题意

https://www.luogu.com.cn/problem/P2135
https://www.acwing.com/problem/content/324/
n(n ≤ 200)个不同颜色的方块，被点击的木块以及和它相邻并且同色的木块就会消除，一次性消除了 k 个木块，那么就会得到 k * k 分，求最高得分

分析

关键词：相邻消除

考虑区间dp，决策时将中间的视为子问题，连成一片后再消除；

发现若在一个区间内考虑所有颜色的消除，不可实现，故只考虑端点颜色木块的消除（只消除端点，或消除端点和之后的）；

突破口：然而若枚举所有相同颜色块的选择情况复杂度过高（2^n），考虑只考虑端点的(1)和与之相邻的(2)相同颜色区间，消掉中间的部分，然后给(2)加上(1)的影响，再以加上(1)影响的(2)为下一个子问题，考虑(2)怎么消除（若要消除，则由于加上了(1)的影响，相当于连(1)一起消除），将这个影响也设计为状态；

f [ le ] [ ri ] [ k ] 表示 le 到 ri ,当它的右边跟了 k 个与右端点相同颜色的木块时（加上了“影响”），得分的最高值。

注意：太多没有用的状态，为节约时间，可采用记忆性搜索

代码

LL dp(LL le, LL ri, LL k)
{
	if(le > ri) return 0;
	if(le == ri) return f[le][ri][k] = (1 + k) * (1 + k);
	if(f[le][ri][k] > 0) return f[le][ri][k];
	LL j = ri;
	while(j - 1 >= le && a[j - 1] == a[ri]) j--;//找到右端点的相同颜色区间
	f[le][ri][k] = dp(le, j - 1, 0) + (ri - j + 1 + k) * (ri - j + 1 + k);//不与其他块一起消除
	for(int i = le; i < j; i++)//遍历其他块
		if(a[i] == a[ri] && a[i] != a[i + 1])
			f[le][ri][k] = max(f[le][ri][k], dp(le, i, ri - j + 1 + k) + dp(i + 1, j - 1, 0));//加上“影响”
	return f[le][ri][k];