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 此最相思 阅读(434) 评论(0)  编辑 收藏 引用


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