【题意】 你们中的一些人可能玩过一个叫做消木块的游戏。 n个木块排成一列，每个木块都有一个颜色。 例如下图中木块的颜色分别为：金，银，银，银，银，铜，铜，铜，金。
每次，你都可以点击一个木块，这样被点击的木块以及和它相邻并且同色的木块就会消除。 如果一次性消除了k个木块，那么就会得到k*k分。 例如下图所示，点击银色木块，四个木块被消去，得到16分。 给定你一个游戏初始状态，请你求出最高得分是多少。 【输入格式】 第一行包含整数t，表示共有t组测试数据。 每组数据第一行包含整数n，表示共有n个木块。 第二行包含n个整数，表示n个木块的颜色。 代表木块颜色的整数范围是1~n。 【输出格式】 每组数据输出一个结果，每个结果占一行。 输出格式为“Case x: y”，其中x为数据组别编号，从1开始，y为结果。 【数据范围】 1≤t≤100 1≤n≤200 【输入样例】 2 9 1 2 2 2 2 3 3 3 1 1 1 【输出样例】 Case 1: 29 Case 2: 1
step1:
理所当然地想到用区间动态规划，f[x][y]定义为区间x~y的最大得分想法大概就是：每个区间的得分方法有两种第一种：劈成两半，也就是：第二种：若两端木块相同，可以先将中间的消掉，使两端合并，再将其消掉。假设，左端长度为a，右端长度为b，中间是i~j，也就是：代码如下 #include<cstdio> #include<cstring> #include<iostream> #include<algorithm> using namespace std; inline int read() { char c=getchar();int f=1,s=0; while(!isdigit(c)){if(c=='-')f=-1;c=getchar();} while(isdigit(c)){s=s*10+c-'0';c=getchar();} return f*s; } int t,n; int a[210]; int f[210][210]; int fro[210],bac[210]; inline int mymax(int x,int y){return x>y?x:y;} int main() { t=read(); for(int tt=1;tt<=t;tt++) { n=read(); int st,ed,kk; memset(f,0,sizeof(f)); memset(a,0,sizeof(a)); memset(fro,0,sizeof(fro)); memset(bac,0,sizeof(bac)); for(int i=1;i<=n+1;i++) { if(i<=n)a[i]=read(); else a[i]=-99999; if(a[i]!=a[i-1]) { ed=i-1; if(ed!=0)f[st][ed]=(ed-st+1)*(ed-st+1); st=i; } fro[i]=st; } for(int j=n;j>=1;j--) { if(a[j]!=a[j+1])kk=j; bac[j]=kk; } for(int len=2;len<=n;len++) { for(int i=1;i+len-1<=n;i++) { int j=i+len-1; if(a[i]==a[j]) { int th=bac[i]; int tq=fro[j]; if(th<tq)f[i][j]=mymax(f[i][j],(th-i+1+j-tq+1)*(th-i+1+j-tq+1)+f[th+1][tq-1]); } for(int k=i;k<j;k++)f[i][j]=mymax(f[i][j],f[i][k]+f[k+1][j]); } } printf("Case %d: %d\n",tt,f[1][n]); } return 0; } 可能是数据太水的缘故，这种做法居然能得80分但是，客观现实是，这种做法并不正确。为什么？将下组数据带入，正确答案应该是44 ，但是代码却输出281 10 1 1 2 2 1 1 3 3 1 1 因为上述思路可以将两端合并，但是却不能将三端及其以上合并。例如，它会先 处理 2 2 然后使 2 2 前面的 1 1 和 2 2 后面的 1 1 合并，变成 1 1 1 1或者，它会先 处理 33 然后使 3 3 前面的 1 1 和 3 3 后面的 1 1 合并，变成 1 1 1 1再者，它会先 处理 2 2 1 1 3 3 然后使其前面的 1 1 和后边的 1 1 合并，变成 1 1 1 1但是，它永远没有办法去处理 2 2 和 3 3 然后再变成1 1 1 1 1 1
step2：
然后我换了一种思路对于每一个区间，要么它自己内部全部消消乐，要么它消一部分，留一部分和外面的木块合并形成更大的木块每一个大区间的内部，又可以分成很多的小区间，小区间同样即可以自己全部消消乐，也可以消一部分然后留一部分和大区间内其他的小区间合并成更大木块这里就隐含了一个递归的feel所以我们就可以用递归去解决这个问题f(x,y,cnt)表示现在处理一个 x 到 y 的区间，右边有cnt个和y一样颜色的木块等着我的合并（当然我也可以不合并）如果我选择第一种玩法：即自己全部消消乐那么 f(x,y,cnt)=f(x,y-1,0) + (cnt+1)*(cnt+1) //意思就是右边先将整块消掉，然后留下左边自己去消，并且告诉左边——右边没有木块等着你去合并 所以就是f(x,y-1,0)如果我选择第二种玩法：即先消掉一部分，然后留一部分和外面合并那么我先找到区间中和y颜色相同的木块段（设其左端点为 l1,l2,l3......，其右端点是 r1,r2,r3......，长度分别是 len1，len2，len3......），以每一个不同的si为界限，si左边所有的区间询问 f(x,li,（len1-1）+cnt)，ri右边所有的区间询问 f(ri+1,y,0)意思是，我先将右边的杂色木块自己消消乐，留下左边的木块。左边的木块既可以全部自己消消乐，又因为它有与y同样颜色的木块，所以也可以先合并同色木块，然后接着询问剩下来的区间。 #include<cstdio> #include<cstring> #include<iostream> #include<algorithm> using namespace std; inline int read() { char c=getchar();int f=1,s=0; while(!isdigit(c)){if(c=='-')f=-1;c=getchar();} while(isdigit(c)){s=s*10+c-'0';c=getchar();} return f*s; } int t,n; int f[210][210][210]; int a[210]; int bac[210]; inline int mymax(int x,int y){return x>y?x:y;} inline int pf(int x){return x*x;} inline int dfs(int x,int y,int cnt) { if(y<x)return 0; int &s=f[x][y][cnt]; if(s!=0)return s; s=dfs(x,y-1,0)+pf(1+cnt); for(int k=x;k<y;k++) { if(a[k]!=a[y])continue; int hk=bac[k]; if(hk<y) { s=mymax(s,dfs(x,k,cnt+hk-k+1)+dfs(hk+1,y-1,0)); k=hk+1; } else if(hk==y)s=mymax(s,dfs(x,k,cnt+hk-k)); } return s; } int main() { t=read(); for(int tt=1;tt<=t;tt++) { n=read(); memset(f,0,sizeof(f)); for(int i=1;i<=n;i++)a[i]=read(); int kk; for(int i=n;i>=1;i--) { if(a[i]!=a[i+1])kk=i; bac[i]=kk; } printf("Case %d: %d\n",tt,dfs(1,n,0)); } return 0; }但是我悲剧地发现这样做会超时
step3：缩点
因为一个一个木块地处理实在太慢了，所以我们干脆把相邻的同色木块合并成一个木块，赋予每个木块各自的长度，从而保存原有的特征。同时，这么做也符合题意（一消全消）完美AC #include<cstdio> #include<cstring> #include<iostream> #include<algorithm> using namespace std; inline int read() { char c=getchar();int f=1,s=0; while(!isdigit(c)){if(c=='-')f=-1;c=getchar();} while(isdigit(c)){s=s*10+c-'0';c=getchar();} return f*s; } int t,n,tot; int f[210][210][210]; int a[210]; int len[210]; int bac[210]; inline int mymax(int x,int y){return x>y?x:y;} inline int pf(int x){return x*x;} inline int dfs(int x,int y,int cnt) { if(y<x)return 0; int &s=f[x][y][cnt]; if(s!=0)return s; s=dfs(x,y-1,0)+pf(len[y]+cnt); for(int k=x;k<y;k++) { if(a[k]!=a[y])continue; s=mymax(s,dfs(x,k,len[y]+cnt)+dfs(k+1,y-1,0)); } return s; } int main() { t=read(); for(int tt=1;tt<=t;tt++) { n=read(); memset(f,0,sizeof(f)); memset(a,0,sizeof(a)); memset(len,0,sizeof(len)); tot=0; int last=-1; for(int i=1;i<=n;i++) { int x=read(); if(x!=last) { a[++tot]=x; len[tot]=1; } else len[tot]++; last=x; } printf("Case %d: %d\n",tt,dfs(1,tot,0)); } return 0; }
