misschuer

常用链接

统计

积分与排名

百事通

最新评论

hdu 1513 poj 1159 vijos 1327 Palindrome

http://acm.hdu.edu.cn/showproblem.php?pid=1513
#include <iostream>
using namespace std;
#define M 5002
short dp[ M ][ 3 ];//dp[ i ][ j ]从第i个开始 长度为j的子串最少需要添加几个字符来构成回文
//只有j , j - 1 , j - 2有用所以只要开辟3个就够
char str[ M ];
int main(){
    int i , n , j , k , f;
    while (scanf ("%d%*c" , &n) == 1){
        gets(str);
        dp[ 0 ][ 0 ] = 0;
        for (i = 1;i <= n;++ i){
            dp[ i ][ 1 ] = 0;
            dp[ i ][ 0 ] = 0;
        }

        for (j = 2;j <= n;++ j){
            for (i = 1;i <= n - j + 1;++ i){
                if (str[i - 1] == str[i + j - 2]){
                    dp[ i ][j % 3] = dp[i + 1][(j + 1) % 3];
                }
                else{
                    k = (j + 2) % 3;
                    if (dp[ i ][ k ] < dp[i + 1][ k ])
                        dp[ i ][j % 3] = dp[ i ][ k ] + 1;
                    else
                        dp[ i ][j % 3] = dp[i + 1][ k ] + 1;
                }
            }
        }
        printf ("%d\n" , dp[ 1 ][n % 3]);
    }
    return 0;
}
递推方程
str[i-1]==str[i+j-2] dp[i][j]=dp[i+1][j-2];
str[i-1]!=str[i+j-2] dp[i][j]=MIN(dp[i][j-1],dp[i+1][j-1])+1;

posted on 2010-04-12 12:15 此最相思 阅读(438) 评论(0)  编辑 收藏 引用


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