acwing322消木块

这个题目就当一个见识吧

设f[i][j][k]表示当前的状态是[i,j]并且j后面还有k个与j颜色相同的木块的最大价值

第一种情况，当第j块和第j-1块颜色相同时，f[i][j][k]=f[i][j-1][k+1]

第二种情况，当第j块和第j-1块颜色不同时，考虑最后那一堆颜色相同的怎么消去的

如果这一堆没有跟其他颜色相同的合并，那么对于任意一种操作，我们都可以把消去最后这一堆的子操作放在最开始，即最开始就消掉最后这一堆，而不影响答案，所以我们有$f[i][j][k]=f[i][j-1][0]+(1+k{)}^2$

如果我们要让最后这一堆跟前面的某一堆颜色相同的一起消去，我们不妨设最后第j块与原始序列的第p块挨在了一起

那么我们在消除第j块和第p块这连在一起的一堆之前的操作，一定是分开的，即在[1,p]和[p+1,j-1]这两个区间中间分别进行（因为不能增添木块只能消除），所以我们可以先全部进行[p+1,j-1]这个区间的操作在进行[1,p]这个区间的操作而不影响答案。而且根据以上分析，这个p一定是原始序列某一堆颜色相同的块中最右边的一块，而不会是中间的某一块，所以也就很好枚举了

具体见代码

#include
#include
#include 
using namespace std;
const int N=210;
int f[N][N][N],a[N];
void dp(int i,int j,int k)
{
	if(f[i][j][k]) return;
	if(i==j) {
		f[i][j][k]=(1+k)*(1+k);
		return;
	}
	if(a[j]==a[j-1])
	{
		/*int l=j-1;
		while(a[l]==a[j]) l--;
		if(l==i-1) {
			f[i][j][k]=(j-i+1+k)*(j-i+1+k);
			return;
		}
		dp(i,l+1,k+j-l-1);
		f[i][j][k]=f[i][l+1][k+j-l-1];*/
		dp(i,j-1,k+1);
		f[i][j][k]=f[i][j-1][k+1];
		return;
		//注释的是另一种写法，两种没明显区别
		//但注释的写法确实要好一点，不用调用多次函数 
	}
	for(int l=j-1;l>=i;l--)
	if(a[l]==a[j]&&a[l+1]!=a[j]){
		dp(i,l,k+1),dp(l+1,j-1,0);
		f[i][j][k]=max(f[i][j][k],f[l+1][j-1][0]+f[i][l][1+k]);
	}
	dp(i,j-1,0);
	f[i][j][k]=max(f[i][j][k],f[i][j-1][0]+(1+k)*(1+k));
}
int main()
{
	int t,cnt=0;
	scanf("%d",&t);
	int n;
	while(t--)
	{
		memset(f,0,sizeof(f));
		scanf("%d",&n);
		for(int i=1;i<=n;i++)
		scanf("%d",&a[i]);
		dp(1,n,0);
		cnt++;
		printf("Case %d: %d\n",cnt,f[1][n][0]);
	}
    return 0;
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55

洛谷的讨论区好像还有记忆化搜索的优化，可以看一下