希望的海洋

Ain't about how fast I get there,ain't about what's waiting on the other side

常用链接

统计

最新评论

Dp poj 1159(multiple solutions)

(1)思路:最长公共子序列:ans=L-LCS(s,^s)
(2)DP 状态:dp[i][j]为i to j,需要加入的字符。初始:dp[i][i]=0
         分2种情况:s[i]==s[j]则dp[i][j]=dp[i+1][j-1]
                          s[i]!=s[j]               =Min(dp[i+1][j],dp[i][j-1])+1
            dp[i][j]=cal(i+1,j-1);
            
return dp[i][j];
    }

    
/*dp[i][j]=MIN(cal(i+1,j-1)+2,cal(i+1,j)+1);
    dp[i][j]=MIN(dp[i][j],cal(i,j-1)+1);
*/



    dp[i][j]
=MIN(cal(i+1,j)+1,cal(i,j-1)+1);
    
return dp[i][j];
}
int main()
{
    
int i,j,k,mid;
    scanf(
"%d",&N);
    
//for(i=0;i<N;i++)
        scanf("%s",s);
    len
=strlen(s);
    
//printf("%d\n",len);
    mid=len/2;
    memset(dp,
-1,sizeof(dp));//unsigned to the utmost
    dp[mid][mid]=0;
    
    printf(
"%d\n",cal(0,len-1));
    
return 0;
}

    
(3)节省空间,用dp[2][5002]的数组存放。因为i-1用过后,就不再用了
滚动数组最直接的想法就是利用原来第i-1行的空间来计算接下来要算的i+1行
#include<cstdio>
#include
<cstdlib>
#include
<cstring>
#include
<cmath>
#define MIN(a,b) (a)<(b)?(a):(b)

char s[5002];
int dp[2][5002];
int main()
{
    
int i,j,k,l,N;
    scanf(
"%d",&N);
    scanf(
"%s",s);
    
for(i=N-1;i>=0;i--)
        
for(j=i+1;j<N;++j)
            
if(s[i]==s[j])dp[i&1][j]=dp[(i+1)&1][j-1];
            
else dp[i&1][j]=MIN(dp[(i+1)&1][j]+1,dp[i&1][j-1]+1);
    printf(
"%d\n",dp[(i+1)%2][N-1]);
    
return 0;
}


这样就可以用一个array[2][]的数组,在两行之间交替计算

(4)
特殊情况:计算array[i][j]所用到的第i-1行的元素全部都在j列的左边
array[i-1][j]和array[i-1][j-1]
然后这种情况可以只用一维数组,按照从右到左的顺序计算
array[j] = array[j-1]+array[j]
重复i次
每次从右到左将一行的元素都按照array[j] = array[j-1]+array[j]计算
假设这个一维数组现在存的是i-1行的元素,计算第i行的元素时,直接将它记
录在这个一维数组对应的位置上
因为是从右向左计算,而计算只需要左边的元素,所以新存进去的元素不会影响后面元素的值

#include <stdio.h>
#include 
<string.h>
int main()
{    
    
char a[5002];
    
int f[5002];
    
int i,j,n,t,tp;
    scanf(
"%d%s",&n,a+1);

    memset(f,
0,sizeof(f));
    
for(i=1;i<=n;i++){
        tp
=0;    //f[i-1,j-1]复位,一开始忘记了,老是wa,郁闷
        for(j=n;j>=1;j--){
            
if(a[i]==a[j]){
                t
=f[j];
                f[j]
=tp+1;    //f[i,j]=f[i-1,j-1]+1
                tp=t;        
            }

            
else{
                tp
=f[j];
                
if(f[j]<f[j+1]) f[j]=f[j+1]; //f[i-1,j]<f[i,j-1]
            }

        }

    }

    printf(
"%d\n",n-f[1]);
    
return 0;
}




posted on 2011-08-19 15:12 拥梦的小鱼 阅读(242) 评论(0)  编辑 收藏 引用 所属分类: POJ


只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理