Codeforces 1132F Clear the String（区间dp）

传送门

题意：给一个长度不超过500的字符串，每次可以消掉字符串中连续相同的一个子串，消去之后剩下的两个串自动连在一起，问最少消多少次使字符串清空。

题解：区间dp，一看应该使的但是第一把居然写出来个的。过了样例交上去果然WA了，原因是没有考虑最优解是讲原串分成若干子串的情况。所以转移时需要引入断点k，从而复杂度多一个n。

比如

6

adabcb

就可以卡掉这个会WA的算法（正解在后面）

#include<cstdio> #include<cstring> #include<iostream> #include<algorithm> using namespace std; const int INF=0x3f3f3f3f; const int N=504; int n; char s[N]; int f[N][N]; inline int read() { int x=0,f=1;char c=getchar(); while (c<'0'||c>'9') {if (c=='-') f=-1;c=getchar();} while (c>='0'&&c<='9') x=x*10+c-'0',c=getchar(); return x*f; } inline void smin(int &x,int y) { x=x>y?y:x; } int main() { // freopen("in.txt","r",stdin); n=read(); scanf("%s",s+1); memset(f,INF,sizeof(f)); for (register int i=1;i<=n;++i) f[i][i]=1; for (int len=2;len<=n;++len) for (int i=1;i+len-1<=n;++i) { int j=i+len-1; f[i][j]=min(f[i+1][j]+1,f[i][j-1]+1); if (s[i]==s[j]||s[i]==s[i+1]) smin(f[i][j],f[i+1][j]); if (s[i]==s[j]||s[j]==s[j-1]) smin(f[i][j],f[i][j-1]); } /* for (int i=1;i<=n;++i) { for (int j=1;j<=n;++j) printf("%-2d ",f[i][j]==INF?-1:f[i][j]); puts(""); }*/ printf("%d\n",f[1][n]); return 0; }

正解

#include<cstdio> #include<cstring> #include<iostream> #include<algorithm> using namespace std; const int INF=0x3f3f3f3f; const int N=504; int n; char s[N]; int f[N][N]; inline int read() { int x=0,f=1;char c=getchar(); while (c<'0'||c>'9') {if (c=='-') f=-1;c=getchar();} while (c>='0'&&c<='9') x=x*10+c-'0',c=getchar(); return x*f; } inline void smin(int &x,int y) { x=x>y?y:x; } int main() { // freopen("in.txt","r",stdin); n=read(); scanf("%s",s+1); memset(f,INF,sizeof(f)); for (register int i=1;i<=n;++i) f[i][i]=1; for (int len=2;len<=n;++len) for (int i=1;i+len-1<=n;++i) { int j=i+len-1; for (int k=i;k<j;++k) if (s[i]==s[j]) smin(f[i][j],f[i][k]+f[k+1][j]-1); else smin(f[i][j],f[i][k]+f[k+1][j]); } printf("%d\n",f[1][n]); return 0; }