题意很明确了,像这种消除一小块同色的东西获得一些分数,让你使这个分数最大的题目多半可以考虑区间DP
不妨先试:设 f[l][r] 表示从 l 消到 r 可获得的最大分数。枚举一个中间转移的断点 k
这样设是最直接的状态。最大的问题是这么设中间的颜色非常不好处理,仍然需要再从l 遍历到 k 和从 k + 1 遍历到 r,看颜色是否相同,可以消除。那么这么做的复杂度是 O(n^4)
考虑另一种状态,设 f[l][r][k] 表示从 l 消到 r 并且在 r 后还有 k 个与 r 位置上的方块同色的方块
考虑 k =0 的特殊情况,那么它肯定由右边界的上一个位置 r-1 转移过来,则 f[l][r][0] = max(f[l][r][0],f[l][r - 1][0] + 1)
因为 k=0 也可以写成:f[l][r][0] = max(f[l][r][0],f[l][r - 1][0] + (k+1)^2)
推广到全部情况,设 l \leq p
实现的时候借鉴了神tst的预处理每一个位置上颜色相同的个数的方法,具体实现见代码。
类似的比较巧妙的区间DP推荐:P3147 [USACO16OPEN]262144
Code
#include <bits/stdc++.h>
using namespace std;
const int SIZE = 200 + 5;
int T, n;
int a[SIZE], sum[SIZE], f[SIZE][SIZE][SIZE];
namespace ae86 {
const int bufl = 1 << 15;
char buf[bufl], *s = buf, *t = buf;
inline int fetch() {
if (s == t) { t = (s = buf) + fread(buf, 1, bufl, stdin); if (s == t) return EOF; }
return *s++;
}
inline int read() {
int a = 0, b = 1, c = fetch();
while (!isdigit(c))b ^= c == '-', c = fetch();
while (isdigit(c)) a = a * 10 + c - 48, c = fetch();
return b ? a : -a;
}
}
using ae86::read;
inline void init()
{
memset(f, 0, sizeof(f));
memset(sum, 0, sizeof(sum));
}
int main()
{
// freopen("data.in", "r", stdin);
// freopen("data.out", "w", stdout);
T = read();
int ind = 0;
while (T--) {
ind++;
n = read();
for (int i = 1; i <= n; i++) a[i] = read();
for (int i = n - 1; i >= 1; i--)
for (int j = i + 1; j <= n; j++) {
if (a[i] == a[j]) sum[i]++;
}
for (int i = n; i >= 1; i--)
for (int j = i; j <= n; j++) {
for (int k = i; k < j; k++) {
if (a[j] == a[k]) {
for (int p = 0; p <= sum[k]; p++)
f[i][j][p] = std::max(f[i][j][p], f[k + 1][j - 1][0] + f[i][k][p + 1]);
}
}
for (int k = 0; k <= sum[j]; k++) {
f[i][j][k] = std::max(f[i][j][k], f[i][j - 1][0] + (k + 1) * (k + 1));
}
}
std::cout << "Case " << ind << ": " << f[1][n][0] << endl;
init();
}
return 0;
}
Comments | NOTHING