P2135 题解
wangyibo201026
·
·
题解
思路
首先考虑区间 DP，那么设 f_{i, j} 为颜色块 i 到颜色块 j 全部消完的最大价值。那么转移显然可以这么写：
f_{i, j} = \max(f_{i, j}, f_{i, k} + f_{k + 1, j})
此时 k 为枚举的断点，但是显然不够，因为可能出现这种情况：
此时明显 f_{i, k} + f_{k + 1, j} 就不是最优的消除方案，因该先把蓝色的全部消掉，再消红色的。
但最大的问题还不是这个，请看图：
此时 l 是在枚举断点时的一个断点，那么最优方案此时就不是 f_{i, l} + f_{l + 1, j}，因为明显是要红色的连起来消最优。
很明显，以上情况用两维的 f 都无法解决，所以我们再开一维：
此时又两种转移：
1. 在 $j$ 后面补上 $k$ 位（注意：并非指块）：
$$f_{i, j, k} = \max(f_{i, j, k}, f_{i, j, 0} + (num_j + k) ^ 2)$$
2. $k$ 为 $[i, j]$ 断点，当 $color_k = color_j$ 时，合并 $[i, j]$ 和 $j$ 以及 $j$ 后面 $t$ 位：
$$f_{i, j, t} = \max(f_{i, j, t}, f_{i, k, num_j + t} + f_{k + 1, j - 1, 0})$$
此时只需预处理出 $suf_i$ 表示 $i$ 色块后面有多少个连续位置的颜色与 $i$ 相同就可以了。
## 代码
Code：
```cpp
#include<bits/stdc++.h>
using namespace std;
const int N = 505;
int n;
int color[N], num[N], suf[N], f[N][N][N];
int main(){
scanf("%d", &n);
for(int i = 1; i <= n; i++){
cin >> color[i];
}
for(int i = 1; i <= n; i++){
cin >> num[i];
}
for(int i = 1; i <= n; i++){ //预处理出 suf[i]
for(int j = i + 1; j <= n; j++){
if(color[i] == color[j]){
suf[i] += num[j];
}
}
}
memset(f, 0xcf, sizeof(f));
for(int i = 1; i <= n; i++){
for(int j = 0; j <= suf[i]; j++){
f[i][i][j] = (num[i] + j) * (num[i] + j); //这里预处理出 f 数组
}
}
for(int len = 2; len <= n; len++){
for(int i = 1; i + len - 1 <= n; i++){
int j = i + len - 1;
for(int k = 0; k <= suf[j]; k++){ //注意：0 也可以
f[i][j][k] = max(f[i][j][k], f[i][j - 1][0] + (num[j] + k) * (num[j] + k));
}
for(int k = i; k <= j - 2; k++){ //这里为什么 j - 1 不行，因为要删掉 k + 1 到 j - 1 的，而 k = j - 1 是无效的
if(color[k] == color[j]){
for(int t = 0; t <= suf[j]; t++){
f[i][j][t] = max(f[i][j][t], f[i][k][num[j] + t] + f[k + 1][j - 1][0]); //这里为什么是 num[j] + t，因为 k 和 j 合并了，所以 j 后面一共有 num[j] + t 个
}
}
}
}
}
printf("%d\n", f[1][n][0]);
return 0;
}
```
本题真的很难，如果有不理解可以私信。