题目描述
You are given several boxes with different colors represented by different positive numbers.
You may experience several rounds to remove boxes until there is no box left. Each time you can choose some continuous boxes with the same color (i.e., composed of k boxes, k >= 1), remove them and get k * k points.
Return the maximum points you can get.
(区间DP) $O(n^4)$
- 状态表示:因为合并一段区间的木块后,可能还会触发和该区间相邻的同色木块的消除,所以用$f[l,r,k]$表示消除$[l,r]$这一段木块,并且$[r,r+k]$这一段木块的颜色相同时,能获得的最高得分。
- 状态转移:因为$[r,r+k]$这一段木块的颜色相同,所以可以合并$[r,r+k]$这一段木块,也可以把$r$和$[l,r-1]$中某块和$r$颜色相同的木块(假设为$i$)之间的木块消除,两种情况分别对应如下转移:
- 合并$[r,r+k]$这一段木块:$f[l,r,k]=f[l,r-1,0]+(k+1)^2$
- 从$[l,r-1]$中找一块和$r$同色的木块$i$,把$[i+1,r-1]$之间的木块都消除,之后就可以消除$i$和$[r,r+k]$这$k+1$块同色木块了:$f[l,r,k]= \overset {color_i=color_r} {\underset {l\le i < r} {max}} \{f[l,i,k+1]+f[i+1,r-1,0]\}$
- 用$s[i,j]$表示下标大于等于$i$的木块中颜色为$j$的木块数量,在对$r$的右边颜色和$r$相同的木块转移时,该段木块数量(长度)的取值在$[0,s[r+1,color_i]]$之间;
- 用$nxt[i,j]$表示下标大于等于$i$的木块中最靠左的颜色为$j$的木块的下标,假设$k=nxt[l,color_r]$,那么在枚举$[l,r]$之间的和$r$颜色相同的木块进行转移时,这些木块的下标可以通过$k=nxt[k+1,color_r]$来获取,进而优化转移的速度。
参考文献
- 参考 AcWing 322. 消木块 。
C++ 代码
class Solution {
private:
int f[102][102][102], s[102][102], nxt[102][102], a[102];
public:
int removeBoxes(vector<int>& boxes) {
int n = boxes.size();
for (int i = 1; i <= n; ++i) a[i] = boxes[i - 1];
for (int i = 1; i <= 100; ++i) nxt[n + 1][i] = n + 1;
for (int i = n; i >= 1; --i)
for (int j = 1; j <= 100; ++j) {
s[i][j] = s[i + 1][j] + (a[i] == j);
if (a[i] == j) nxt[i][j] = i;
else nxt[i][j] = nxt[i + 1][j];
}
for (int len = 1; len <= n; ++len)
for (int l = 1; l + len - 1 <= n; ++l) {
int r = l + len - 1;
for (int i = 0; i <= s[r + 1][a[r]]; ++i) {
f[l][r][i] = f[l][r - 1][0] + (i + 1) * (i + 1);
for (int k = nxt[l][a[r]]; k < r; k = nxt[k + 1][a[r]])
f[l][r][i] = max(f[l][r][i], f[l][k][i + 1] + f[k + 1][r - 1][0]);
}
}
return f[1][n][0];
}
};