POJ 1458 1159

http://poj.org/problem?id=1458

一道容易的DP,求最长公共子序列的

dp[i][j],代表str1中的第i个字母和str2中的第j个字母的最多的公共字母数

 #include <stdio.h>
 #include <iostream>
 #include <string.h> using namespace std;
 int dp[][]={}; int main()
 {
     char str1[],str2[];
     while(~scanf("%s %s",str1,str2))
     {
      /*   scanf("%s",str1)
         scanf("%s",str2);*/
         int len1=strlen(str1);
         int len2=strlen(str2);
         for(int i=;i<=len1;i++)
             for(int j=;j<=len2;j++)
         {
             if(str1[i-]==str2[j-]) dp[i][j]=dp[i-][j-]+; //这个就是那个递推公式，但str1[i-1]和str2[j-1]想等于时dp[i][j]就会等于前一个加一，不等就是等于前面的最大的一个
             else dp[i][j]=max(dp[i-][j],dp[i][j-]);
         }
         printf("%d\n",dp[len1][len2]);
     }
     return ;
 }

http://poj.org/problem?id=1159

这个是POJ1159的题目，试求插入的最少的字符，使其变成回文字符串

这个最少的字符MIN=N-N和N的逆序数的最长公共子序列

所以这道题也就是和上面的那个题目一样，求最长的公共子序列，不过有一个地方比上面要特殊一点，就是数组只可以开滚动数组，不然POJ就爆内存

也只是在部分地方进行了改动即可

在这里也使用了一个我以前从未用过的函数，reverse ，这个函数在algorithm的头文件里

作用是把远数组变成逆序的，使用方法也就是reverse(begin(),end());

 #include <stdio.h>
 #include <iostream>
 #include <string>
 #include <string.h>
 #include <algorithm> using namespace std; int dp[][];
 string str1,str2; int main(){
     int n;
     while(scanf("%d",&n)!=EOF){
         cin>>str1;
         str2=str1;
         memset(dp,,sizeof(dp));
         reverse(str2.begin(),str2.end());
         for(int i=;i<=n;i++)
             for(int j=;j<=n;j++){
                 if(str1[i-]==str2[j-]){
                     int tem=dp[(i-)%][j-]+;   //这个和上面的不同的原因在于这个是滚动数组，而滚动数组的话，原数组一般都是有值的，只不过是新的值在原数组上进行覆盖而已，求最大的公共子序列，就不能排除原来的数组的dp[i%2][j]会小于tmp；
                     dp[i%][j]=max(dp[i%][j],tem);
                 }
                 else dp[i%][j]=max(dp[(i-)%][j],dp[i%][j-]);
             }
         cout<<n-dp[n%][n]<<endl;
     }
     return ;
 }