参考 https://www.cnblogs.com/Tieechal/p/11637638.html
┭┮﹏┭┮
$f(l, r, k)$ 表示 消除 (
$l$ ~ $r$ 和 拼接在 $r$ 之后连续 $k$ 个与 $r$ 颜色相同木块)
的最大值
记忆化搜索
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 210, INF = 0x3f3f3f3f;
int n, cnt, test;
int col[N], len[N];
int f[N][N][N];
int dp(int l, int r, int k)
{
if (l > r) return 0;
if (l == r) return f[l][r][k] = (len[r] + k) * (len[r] + k);
if (~f[l][r][k]) return f[l][r][k];
f[l][r][k] = dp(l, r - 1, 0) + (len[r] + k) * (len[r] + k);
for (int i = l; i < r; i ++ )
if (col[i] == col[r])
f[l][r][k] = max(f[l][r][k], dp(l, i, len[r] + k) + dp(i + 1, r - 1, 0));
return f[l][r][k];
}
void solve()
{
cnt = 0;
memset(f, -1, sizeof f);
scanf("%d", &n);
int last = 0;
for (int i = 1; i <= n; i ++ )
{
int x;
scanf("%d", &x);
if (x != last) col[ ++ cnt] = x, len[cnt] = 1;
else len[cnt] ++ ;
last = x;
}
printf("Case %d: %d\n", ++ test, dp(1, cnt, 0));
}
int main()
{
int T; scanf("%d", &T);
while (T -- ) solve();
return 0;
}
循环转移会有太多用不到的地方,K 值很多不会取到的, $n ^ {4}$ 超时
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
const int N = 210;
int n, test;
int col[N], sz[N];
int f[N][N][N];
void solve()
{
memset(f, 0, sizeof f);
scanf("%d", &n);
int cnt = 0, last = 0;
for (int i = 1; i <= n; i ++ )
{
int x;
scanf("%d", &x);
if (x != last) col[ ++ cnt] = x, sz[cnt] = 1;
else sz[cnt] ++ ;
last = x;
}
n = cnt;
for (int len = 1; len <= n; len ++ )
for (int l = 1; l + len - 1 <= n; l ++ )
{
int r = l + len - 1;
for (int k = 0; k < N; k ++ )
if (l == r) f[l][r][k] = (sz[r] + k) * (sz[r] + k);
else
{
f[l][r][k] = f[l][r - 1][0] + (sz[r] + k) * (sz[r] + k);
for (int i = l; i < r; i ++ )
if (col[i] == col[r])
f[l][r][k] = max(f[l][r][k], f[l][i][sz[r] + k] + f[i + 1][r - 1][0]);
}
}
printf("Case %d: %d\n", ++ test, f[1][n][0]);
}
int main()
{
int T; scanf("%d", &T);
while (T -- ) solve();
return 0;
}
348