CF1572C Paint
一看感觉很有 dp 的感觉。所以就来吧。
设 \(f_{l,r,c}\) 表示区间 \([l,r]\) 选了颜色 \(c\) 的答案，先不管怎么转移。
状态太巨大，有种猜结论的冲动：若只保留 \(c=a_l\) 和 \(c=a_r\)，答案依旧正确。
考虑证明：答案只和 \(f_{1,n}\) 有关，这时候若对 \(a_1\) 或 \(a_n\) 做了单点染色，则一定可以通过染色补集使得答案不劣。所以我们可以惊喜地发现只需要保留右端点的颜色信息。
现在就有个暴力的转移了。
\[f_{l,r} = \min \{ f_{k,r-1} + 1, \min_k \{ f_{l,k} + f_{k + 1, r} + [a_k \neq a_r] \} \}
\]
这个 \(k\) 一看就能优化。考虑到数据的特殊性质，不难猜出只用枚举相同颜色的 \(k\)，因为剩下的 \(k\) 都可以通过中间的可转移的点最终转移到 \(f_{l,r}\)。那么复杂度就是 \(O(n^2)\)
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
namespace IO {
#define isdigit(x) (x >= '0' && x <= '9')
template<typename T>
inline void read(T &x) {
x = 0; char ch = getchar(); int f = 0;
for(; !isdigit(ch); ch = getchar()) if(ch == '-') f = 1;
for(; isdigit(ch); ch = getchar()) x = x * 10 + ch - '0';
if(f) x = -x;
}
template<typename T>
inline void write(T x) {
if(x < 0) putchar('-'), x = -x;
if(x > 9) write(x / 10);
putchar(x % 10 + '0');
}
#undef isdigit
}
using namespace IO;
const int N = 3e3 + 10;
int n, a[N], las[N], pre[N];
int f[N][N];
inline void upd(int &x, int y) {
x = min(x, y);
}
void solve() {
read(n);
for(int i = 1; i <= n; ++i)
read(a[i]), las[a[i]] = 0;
for(int i = 1; i <= n; ++i) {
pre[i] = las[a[i]];
las[a[i]] = i;
}
for(int len = 2; len <= n; ++len) {
for(int l = 1; l + len - 1 <= n; ++l) {
int r = l + len - 1;
f[l][r] = f[l][r - 1] + 1;
for(int j = pre[r]; j >= l; j = pre[j])
upd(f[l][r], f[l][j] + f[j + 1][r]);
}
}
printf("%d\n",f[1][n]);
}
int main() {
int T; read(T);
while(T--) solve();
}