题目传送门:
题意:给出一个长为$N$的串,可以每次消除颜色相同的一段并获得其长度平方的分数,求最大分数。数据组数$\leq 15$,$N \leq 200$
DP好题,状态转移方程可能这辈子都不会想出来$qwq$ 看完题就知道是区间DP,设状态为$f_{i,j}$,然后考虑转移的时候发现:中间可能有一部分零散的和两端相同颜色的块,转移十分麻烦 于是考虑神仙状态:$f_{i,j,k}$,其中$i,j$同上,$k$表示 在块$j$之后有且仅有$k$个与块$j$相同颜色的块 考虑转移:分两种情况 $a.$把最后$k+1$个一起消掉,由$f_{i,j-1,0}+(k+1)^2$转移 $b.$在$[i,j-1]$中取一个块$m$满足$color_m=color_j$,将它们中间的元素消掉,也就是由$f_{m+1,j-1,0}+f_{i,m,k-1}$转移 将以上转移取$max$即可 关于为什么是对的就感性理解一下吧 一定要注意转移顺序啊$qwq$ 复杂度是$O(n^4)$,复杂度不对竟然在$UVA$和$POJ$上效率还可以
1 #include2 using namespace std; 3 inline int read(){ 4 int a = 0; 5 char c = getchar(); 6 while(!isdigit(c)) 7 c = getchar(); 8 while(isdigit(c)){ 9 a = (a << 3) + (a << 1) + (c ^ '0');10 c = getchar();11 }12 return a;13 }14 inline int max(int a , int b){15 return a > b ? a : b;16 }17 int ans[201][201][201] , col[201] , dis[201];18 int main(){19 int T = read();20 for(int i = 1 ; i <= T ; i++){21 int N = read();22 memset(ans , 0 , sizeof(ans));23 memset(dis , 0 , sizeof(dis));24 for(int j = 1 ; j <= N ; j++)25 col[j] = read();26 for(int j = N ; j ; j--)27 for(int k = j + 1 ; k <= N ; k++)28 if(col[j] == col[k])29 dis[j]++;30 for(int j = N ; j ; j--)31 for(int k = j ; k <= N ; k++){32 for(int q = j ; q < k ; q++)33 //转移顺序很重要!34 if(col[q] == col[k])35 for(int p = 0 ; p <= dis[k] ; p++)36 ans[j][k][p] = max(ans[j][k][p] , ans[q + 1][k - 1][0] + ans[j][q][p + 1]);37 for(int p = 0 ; p <= dis[k] ; p++)38 ans[j][k][p] = max(ans[j][k][p] , ans[j][k - 1][0] + (p + 1) * (p + 1));39 }40 printf("Case %d: %d\n" , i , ans[1][N][0]);41 }42 return 0;43 }