题解：P2135 方块消除
DiaoHantong
·
·
题解
题目传送门
思路
这道题一看就是区间DP，每消除一个区域的方块，就可以得到 b_i^2 的分数，假设 f_{i,j} 为消除区间 [i,j] 的最高分，那么，对于区域 j ，就有两种决策：
决策1：消除区域 j，那么 f_{i,j}=f_{i,j-1}+b^2_i
决策2：暂时不消除区域 j,与之前的某个同色块连在一起消除，但对于决策2，我们需要清楚知道区间 [i,j-1] 中每一个区域的消除情况，状态数过多，我们可以换一种思路。
决策2会对未来行动产生影响，所以我们可以再加一个维度来假设未来情况。
设 f_{i,j,k} 表示消除区间 [i,j] 且区域 j 之后有 k 个与区域 j 同色的方块的最大得分，对于区域 j，有以下两种决策：
决策1：消除区域 j 和与之相连的 k 个同色方块，那么 f_{i,j,k}=f_{i-1,j-1,0}+(b_j+k)^2。
决策2：暂时不消除区域 j 区域，与之前的某个同色区域连在一起消除。假设区间 [i,j-1] 中与区域 j 同色的区域所在位置为 p，那么 f_{i,j,k}=f_{i,p,k+b_j}+f_{p+1,j-1,0} 。
综上所述，
边界为 $f_{i,j,k}=0,f_{i,i,k}=(b_i+k)^2$ ,
即消除区间 $[i,i]$ 的方块且区域 $i$ 之后有 $k$ 个与区域 $i$ 同色的方案最大得分为 $(b_i+k)^2$。
目标解为 $f_{1,n,0}$ ,即消除区域 $[1,n]$ 的方块且区域 $n$ 后有 $0$ 个与区域 $n$ 同色的方块的最大得分。
## 代码
```cpp
#include<bits/stdc++.h>
using namespace std;
int c[55],b[55];
long long f[55][55][1005];
//f[i][j][k]代表消除区间[i,j]的方块且区域j之后(未来)有k个与区域j同色的方块的最大得分
int main(){
int n,s=0;
cin>>n;
for(int i=1;i<=n;i++)cin>>c[i];
for(int i=1;i<=n;i++)cin>>b[i],s+=b[i];
for(int len=1;len<=n;len++){//枚举阶段
for(int i=1;i+len-1<=n;i++){//枚举状态
int j=i+len-1;
for(int k=0;k<=s;k++){//决策1
f[i][j][k]=max(f[i][j][k],f[i][j-1][0]+(b[j]+k)*(b[j]+k));
}
for(int p=i;p<j-1;p++){//决策2
if(c[p]==c[j]){
for(int k=0;k<=s;k++){
f[i][j][k]=max(f[i][j][k],f[i][p][k+b[j]]+f[p+1][j-1][0]);
}
}
}
}
}
cout<<f[1][n][0];//输出目标解f[1][n][0];
return 0;
}
```