51nod 1092 回文字符串 (dp)

时间：2023-07-30 08:50:44

http://www.51nod.com/onlineJudge/questionCode.html#!problemId=1092

这个题是poj-3280的简化版，这里只可以增加字符，设 dp[i][j] 为把以i开头j结尾的子串变为回文串的最少次数，

if(s[i]==s[j])  dp[i][j]=dp[i+1][j-1];

else dp[i][j]=min(dp[i+1][j],dp[i][j-1])+1;

 #include <iostream>

 #include <cstdio>

 #include <cmath>

 #include <vector>

 #include <cstring>

 #include <string>

 #include <algorithm>

 #include <string>

 #include <set>

 #include <functional>

 #include <numeric>

 #include <sstream>

 #include <stack>

 #include <map>

 #include <queue>

 #pragma comment(linker, "/STACK:102400000,102400000")

 #define CL(arr, val)    memset(arr, val, sizeof(arr))

 #define ll long long

 #define inf 0x7f7f7f7f

 #define lc l,m,rt<<1

 #define rc m + 1,r,rt<<1|1

 #define pi acos(-1.0)

 #define L(x)    (x) << 1

 #define R(x)    (x) << 1 | 1

 #define MID(l, r)   (l + r) >> 1

 #define Min(x, y)   (x) < (y) ? (x) : (y)

 #define Max(x, y)   (x) < (y) ? (y) : (x)

 #define E(x)        (1 << (x))

 #define iabs(x)     (x) < 0 ? -(x) : (x)

 #define OUT(x)  printf("%I64d\n", x)

 #define lowbit(x)   (x)&(-x)

 #define Read()  freopen("a.txt", "r", stdin)

 #define Write() freopen("b.txt", "w", stdout);

 #define maxn 1000000000

 #define N 1010

 #define mod 1000000000

 using namespace std;

 int dp[N][N];

 char s[N];

 int main()

 {

     //Read();

     scanf("%s",s);

     int m=strlen(s);

     memset(dp,,sizeof(dp));

     for(int i=m-;i>=;i--)

     {

         for(int j=i+;j<m;j++)

         {

                 if(s[i]==s[j]) dp[i][j]=dp[i+][j-];

                 else dp[i][j]=min(dp[i+][j],dp[i][j-])+;

                 //printf("%d\n",dp[i][j]);

         }

     }

     printf("%d\n",dp[][m-]);

     return ;

 }

还可以转化为最长公共子序列的问题求解，求最少变成回文串的操作次数，就是求有几个字符与对应的字符不一样，那么只要我把原字符翻转，然后求最长公共子序列，

用字符串长度减去公共子序列长度即可求解。

因为dp[i+1]计算时只用到了dp[i],dp[i+1],所以可以结合奇偶性用滚动数组优化空间。

 #include <iostream>

 #include <cstdio>

 #include <cmath>

 #include <vector>

 #include <cstring>

 #include <string>

 #include <algorithm>

 #include <string>

 #include <set>

 #include <functional>

 #include <numeric>

 #include <sstream>

 #include <stack>

 #include <map>

 #include <queue>

 #pragma comment(linker, "/STACK:102400000,102400000")

 #define CL(arr, val)    memset(arr, val, sizeof(arr))

 #define ll long long

 #define inf 0x7f7f7f7f

 #define lc l,m,rt<<1

 #define rc m + 1,r,rt<<1|1

 #define pi acos(-1.0)

 #define L(x)    (x) << 1

 #define R(x)    (x) << 1 | 1

 #define MID(l, r)   (l + r) >> 1

 #define Min(x, y)   (x) < (y) ? (x) : (y)

 #define Max(x, y)   (x) < (y) ? (y) : (x)

 #define E(x)        (1 << (x))

 #define iabs(x)     (x) < 0 ? -(x) : (x)

 #define OUT(x)  printf("%I64d\n", x)

 #define lowbit(x)   (x)&(-x)

 #define Read()  freopen("a.txt", "r", stdin)

 #define Write() freopen("b.txt", "w", stdout);

 #define maxn 1000000000

 #define N 1010

 #define mod 1000000000

 using namespace std;

 int dp[][N];

 char s[N],ss[N];

 int main()

 {

     //Read();

     scanf("%s",s);

     int m=strlen(s);

     for(int i=;i<m;i++)

         ss[i]=s[m-i-];

     ss[m]='\0';

     memset(dp,,sizeof(dp));

     for(int i=;i<m;i++)

     {

         for(int j=;j<m;j++)

         {

             if(s[i]==ss[j]) dp[(i+) & ][j+]=dp[i & ][j]+;

             else dp[(i+) & ][j+]=max(dp[i & ][j+],dp[(i+) & ][j]);

             //printf("%d\n",dp[i+1][j+1]);

         }

     }

    // printf("%d\n",dp[m][m]);

     printf("%d\n",m-dp[m&][m]);

     return ;

 }

相关文章