华尊世界——打造互联网青年励志规划平台!

 

 

搜索
查看: 1849|回复: 1
go

杭电hdu 1513 dp +优化

Rank: 4Rank: 4Rank: 4Rank: 4

发表于 2011-12-23 21:05 |显示全部帖子
[p=21, null, left]//我个人的理解就是当前行的结果只与前一行的结果有关

[p=21, null, left]//所以每次枚举行的时候滚动数组的行%2;

[p=21, null, left]//就只有0,1,两种状态 也就是两行交替存储答案 。。。就这样的 不然内存不够用的哦

[p=21, null, left]#include<iostream>
#include<string>
using namespace std;
int ans[3][5005];
int max(int a,int b)
{
    if(a>b) return a;
    return b;
}
int main()
{
    int i,j,n;
    char s1[5005],s2[5005];
//   freopen("E:\\test.txt","r",stdin);
    while(cin>>n)
    {
        cin>>s1;
        for(i=0;i<n;i++)
        {
            s2=s1[n-i-1];
        }
  s2[n]='\0';
// cout<<s1<<endl<<s2<<endl;
        memset(ans,0,sizeof(ans));
        for(i=0;i<n;i++)
        {
            ans[0]=0;
        }
        for(i=1;i<=n;i++)
        {
            for(j=1;j<=n;j++)
            {
                if(s2[j-1]==s1[i-1])
                {
                    ans[i%2][j]=ans[(i-1)%2][j-1]+1;
                }
                else
                {
                    ans[i%2][j]=max(ans[(i-1)%2][j],ans[i%2][j-1]);
                }
            }   
        }
        cout<<n-ans[n%2][n]<<endl;
    }
    return 0;
}

Rank: 3Rank: 3Rank: 3

发表于 2011-12-23 22:13 |显示全部帖子
好专业,不懂
你需要登录后才可以回帖 登录 | 注册

Archiver|Unitworld.cn.

GMT+8, 2019-5-20 00:56 , Processed in 0.024072 second(s), 10 queries .

© 2001-2010 华尊世界