删去字符串S中的一些字符,使剩下的字符组成最长的回文串(顺序连接)
区间dp f[i][j]
f[i][j] = f[i+1][j-1] i==j
=min( f[i+1][j] ,f[i][j-1] )
#include<iostream> #include<string> #include <cstring> #include <algorithm> using namespace std; const int N=1005; int f[N][N],n; string g[N][N]; char s[N]; void solve(){ int i,j; n=strlen(s+1); for(i=0;i<=n;i++) for(j=0;j<=n;j++){ f[i][j]=0; g[i][j]=""; } for(i=1;i<=n;i++) f[i][i]=0,g[i][i]=s[i]; for(i=n;i>0;i--) for(j=i;j<=n;j++){ if(i==j) continue; if(s[i]==s[j]){ f[i][j]=f[i+1][j-1]; g[i][j]=s[i]+g[i+1][j-1]+s[i]; } else{ if(f[i][j-1]<f[i+1][j]){ f[i][j]=f[i][j-1]+1; g[i][j]=g[i][j-1]; } else if(f[i][j-1]>f[i+1][j]){ f[i][j]=f[i+1][j]+1; g[i][j]=g[i+1][j]; } else{ f[i][j]=f[i+1][j]+1; g[i][j]=min(g[i+1][j],g[i][j-1]); } } } cout<<g[1][n]<<endl; } int main(){ while(cin>>s+1) solve(); }
标签:字符,min,int,solve,include,uva11404 From: https://www.cnblogs.com/towboa/p/16835740.html