Ural 1635 Mnemonics and Palindromes（DP）-白红宇

Ural 1635 Mnemonics and Palindromes（DP）

阅读量：4450 次

发布时间：2019-06-07

本文共 1258 字，大约阅读时间需要 4 分钟。

题目地址：

又是输出路径的DP。。。连着做了好多个了。

。

状态转移还是挺简单的。要先预处理出来全部的回文串，tag[i][j]为1表示字符串i--j是一个回文串。否则不是回文串。预处理时要用n^2的方法。即枚举回文串中间。能够分奇数和偶数两种分别求一次。

然后dp转移方程为,若tag[j][i]==1,dp[i]=min(dp[i],dp[j-1]+1);

对于最令人讨厌的路径输出。能够用pre来记录回文串前驱分裂点，然后依据这些分裂点来输出。

代码例如以下：

#include 
     
      #include 
      
       #include 
       
        #include 
        
         #include 
         
          #include 
          
           #include 
           
            #include 
            
             #include 
             #include 
              
               #include 
               
                using namespace std;#define LL __int64const int INF=0x3f3f3f3f;char s[5000];int dp[5000], tag[4001][4001], len, pre[4001], a[4001];void init(){ int i, j, k, l, r; memset(tag,0,sizeof(tag)); for(i=0;i
                
                 =len) break; if(s[l]==s[r]) { tag[l][r]=1; } else break; } } for(i=0;i
                 
                  =len) break; if(s[l]==s[r]) { tag[l][r]=1; } else break; } } }}int main(){ int i, j, k, cnt; scanf("%s",s); len=strlen(s); init(); dp[0]=0; memset(pre,-1,sizeof(pre)); for(i=1;i<=len;i++) { dp[i]=dp[i-1]+1; pre[i]=i-1; for(j=1;j
                  
                   dp[j-1]+1) { dp[i]=dp[j-1]+1; pre[i]=j-1; } } } } printf("%d\n",dp[len]); cnt=0; for(i=len;i!=-1;i=pre[i]) { a[++cnt]=i; //printf("%d ",a[cnt-1]); } sort(a+1,a+cnt+1); /*for(i=1;i<=cnt;i++) { printf("%d ",a[i]); }*/ for(i=2;i<=cnt;i++) { for(j=a[i-1];j

转载于:https://www.cnblogs.com/jzssuanfa/p/6803345.html

你可能感兴趣的文章