https://codeforces.com/contest/1922/problem/F
题目大意
给出 $n$ 长的数组和颜色数 $x$，满足 $(1 \le x \le n \le 100)$。数组的值 $a_i \ (1 \le a_i \le x)$ 代表每个位置的颜色。你可以执行以下操作若干次：
选取 $1 \le l \le r \le n$ 和 $1 \le k \le x$，满足 $\forall \ l \le i \le r, a[i] \neq k$。将 $[l, r]$ 这一段所有颜色变为 $k$。
问最少多少次操作可以使整个区间 $[1, n]$ 变为相同颜色。
简要题解
引理：如果某一段 $[l, r]$ 被涂过了，则我们可以将其当做一个整体。
证明：
假设 $f(A)$ 表示 $A$ 的整段同色的最少操作次数。$A'$ 表示将 $[l, r]$ 的段缩成段首元素一个之后的数组。
可以证明 $f(A) \ge f(A')$。考虑我们总可以把对于 $A$ 相同的操作应用在 $A'$，得到同色数组。当且仅当 $A$ 的操作 $[l_i, r_i]$ 只与 $[l + 1, r]$ 的元素有关时舍去。 当 $l < l_i \le r$ 时我们将 $l_i$ 调整到 $r + 1$。
可以证明 $f(A) \le f(A')$。考虑对于 $A'$ 的最优操作，我们总可以把对于 $l$ 一个点的操作变为对于 $[l, r]$ 在 $A$ 上一段的操作。因此 $A$ 的最优操作不会更差。
从而我们可以得出 $f(A) = f(A')$。
有了这个基础之后，我们就可以对原问题进行区间 $dp$ 的处理了。
$dp[l][r][c]$ 代表 $[l, r]$ 区间全部涂成颜色 $c$ 的代价。但是我们注意到这是不够的，因为处理完小区间并不总是需要将其涂成同一种颜色，只要其不包含颜色 $c$ 则我们依然可以通过一次操作将其变为全 $c$ 的区间。 因此增加 $dpn[l][r][c]$ 代表 $[l, r]$ 区间全部都不是颜色 $c$ 的最小代价。
我们按照区间长度转移。显然这两组都可以从更短区间转移来，枚举中点合并即可。接下来考虑最后要将区间 $[l, r]$ 刷成某种颜色转移。
$$ \begin{align} dp[i][j][c] & \gets dpn[i][j][c] + 1, \\ dpn[i][j][c] & \gets dp[i][j][d], \quad d \neq c \\ \end{align} $$我们发现这里转移成环了。
dp[i][j][c] <- dpn[i][j][c] <- dp[i][j][d] <- dpn[i][j][d] <- dp[i][j][c]
这不是先有鸡先有蛋了吗？
但是，我们注意到一个区间最多只需要涂色两次。涂色三次，要么相当于涂色一次（$121$ 涂回最初的颜色），要么中间的一次是没意义的（$123$ 相当于 $12$）。于是我们将从合并小区间的结果再用 $[l, r]$ 其他情况来的转移跑两遍就好了。
复杂度
$T$：$O(n ^ 3 \cdot x)$
$S$：$O(n ^ 2 \cdot x)$
代码实现
#include <bits/stdc++.h>
using namespace std;
int io_=[](){ ios::sync_with_stdio(false); cin.tie(nullptr); return 0; }();
using LL = long long;
using ULL = unsigned long long;
using LD = long double;
using PII = pair<int, int>;
using VI = vector<int>;
using MII = map<int, int>;
template<typename T> void cmin(T &x,const T &y) { if(y<x) x=y; }
template<typename T> void cmax(T &x,const T &y) { if(x<y) x=y; }
template<typename T> bool ckmin(T &x,const T &y) {
return y<x ? (x=y, true) : false; }
template<typename T> bool ckmax(T &x,const T &y) {
return x<y ? (x=y, true) : false; }
template<typename T> void cmin(T &x,T &y,const T &z) {// x<=y<=z
if(z<x) { y=x; x=z; } else if(z<y) y=z; }
template<typename T> void cmax(T &x,T &y,const T &z) {// x>=y>=z
if(x<z) { y=x; x=z; } else if(y<z) y=z; }
// mt19937 rnd(chrono::system_clock::now().time_since_epoch().count());
// mt19937_64 rnd_64(chrono::system_clock::now().time_since_epoch().count());
/*
---------1---------2---------3---------4---------5---------6---------7---------
1234567890123456789012345678901234567890123456789012345678901234567890123456789
*/
const int M = 105;
int dp[M][M][M], dpn[M][M][M];
void solve() {
int n, x; cin >> n >> x;
vector<int> a(n);
for (int& i : a) {
cin >> i; i--;
}
if (x == 1) {
cout << "0\n";
return;
}
for (int i = 0; i < n; i++) {
for (int j = i; j < n; j++) {
for (int k = 0; k < x; k++) {
dp[i][j][k] = n;
dpn[i][j][k] = n;
}
}
}
for (int i = 0; i < n; i++) {
for (int c = 0; c < x; c++) {
dp[i][i][c] = (a[i] != c);
dpn[i][i][c] = (a[i] == c);
}
}
for (int len = 2; len <= n; len++) {
for (int l = 0, r = len - 1; r < n; l++, r++) {
for (int c = 0; c < x; c++) {
for (int i = l; i < r; i++) {
cmin(dp[l][r][c], dp[l][i][c] + dp[i + 1][r][c]);
}
for (int i = l; i < r; i++) {
cmin(dpn[l][r][c], dpn[l][i][c] + dpn[i + 1][r][c]);
}
}
for (int i = 0; i < 2; i++) {
int mndp1 = n, mndp2 = n, mndpn = n;
for (int c = 0; c < x; c++) {
cmin(mndp1, mndp2, dp[l][r][c]);
cmin(mndpn, dpn[l][r][c]);
}
for (int c = 0; c < x; c++) {
cmin(dpn[l][r][c], mndp1 == dp[l][r][c] ? mndp2 : mndp1);
cmin(dp[l][r][c], min(mndp1, mndpn) + 1);
}
}
// for (int c = 0; c < x; c++) {
// cerr << l << ' ' << r << ' ' << c << ' ' << dp[l][r][c] << ' ' << dpn[l][r][c] << endl;
// }
}
}
int ans = n;
for (int i = 0; i < x; i++) {
cmin(ans, dp[0][n - 1][i]);
}
cout << ans << '\n';
}
int main() {
int t = 1;
cin >> t;
while (t--) {
solve();
}
return 0;
}
标答做法
更模式化的解决环的办法大概是，直接找到其中某些值的最优解！
对于 $dp[l][r][c]$ 如果 $a[l] = c$ 则 $dp[l][r][c]$ 与 $dp[l + 1][r][c]$ 的结果应该相同。
证明：
考虑操作序列 $op$。如果 $op_i$ 操作的区间不包含 $l$ 则无所谓。如果为 $[l, x]$ 刷成 $c$ 则显然它满足操作时 $a[l, x] \neq c$，同理将这个操作变为 $[l + 1, x]$ 则 $a[l + 1, x] \neq c$ 还成立。因此 $dp[l][r][c] \ge dp[l + 1][r][c]$。
同理因为有转移 $dp[l][r][c] = dp[l][l][c] + dp[l + 1][r][c]$ 其中 $dp[l][l][c] = 0$ 则 $dp[l][r][c] \le dp[l + 1][r][c]$。得出 $dp[l][r][c] = dp[l + 1][r][c]$。
同理，不太显然的，对于 $dpn[l][r][c]$ 如果 $a[l] \neq c$ 则 $dpn[l][r][c]$ 与 $dpn[l + 1][r][c]$ 也是相同的，但其实这里证明是和 $dp$ 的完全一致的。
右边界的讨论是同样的。
如此我们说如果区间 $[l, r]$ 的端点 $a[l] = c, a[r] = d$：
- $c = d$。这种情况，我们可以直接得出所有的 $dpn[l][r][e] \ (e \neq c)$ 和 $dp[l][r][c]$
color dp dpn
0 v
1 v
. v
c v
. v
进一步由 $dp[l][r][e] \gets dpn[l][r][e] + 1$ 的转移得到所有 $dp[l][r][e]$ 的值
color dp dpn
0 v v
1 v v
. v v
c v
. v v
最后由所有 $dp[l][r][e]$ 的值推导出 $dpn[l][r][c]$ 的值。
color dp dpn
0 v v
1 v v
. v v
c v v
. v v
- $c \neq d$。 不妨设 $c < d$。此时分别靠缩短左右边界即可得到所有的 $dpn[l][r][e]$ 的值。
color dp dpn
0 v
1 v
. v
c v v
. v
d v v
. v
进一步由 $dp[l][r][e] \gets dpn[l][r][e] + 1$ 的转移得到所有 $dp[l][r][e]$ 的值
color dp dpn
0 v v
1 v v
. v v
c v v
. v v
d v v
. v v
复杂度是一样的，代码如下
#include <bits/stdc++.h>
using namespace std;
int io_=[](){ ios::sync_with_stdio(false); cin.tie(nullptr); return 0; }();
using LL = long long;
using ULL = unsigned long long;
using LD = long double;
using PII = pair<int, int>;
using VI = vector<int>;
using MII = map<int, int>;
template<typename T> void cmin(T &x,const T &y) { if(y<x) x=y; }
template<typename T> void cmax(T &x,const T &y) { if(x<y) x=y; }
template<typename T> bool ckmin(T &x,const T &y) {
return y<x ? (x=y, true) : false; }
template<typename T> bool ckmax(T &x,const T &y) {
return x<y ? (x=y, true) : false; }
template<typename T> void cmin(T &x,T &y,const T &z) {// x<=y<=z
if(z<x) { y=x; x=z; } else if(z<y) y=z; }
template<typename T> void cmax(T &x,T &y,const T &z) {// x>=y>=z
if(x<z) { y=x; x=z; } else if(y<z) y=z; }
// mt19937 rnd(chrono::system_clock::now().time_since_epoch().count());
// mt19937_64 rnd_64(chrono::system_clock::now().time_since_epoch().count());
/*
---------1---------2---------3---------4---------5---------6---------7---------
1234567890123456789012345678901234567890123456789012345678901234567890123456789
*/
const int M = 105;
int dp[M][M][M], dpn[M][M][M];
void solve() {
int n, x; cin >> n >> x;
vector<int> a(n);
for (int& i : a) {
cin >> i; i--;
}
if (x == 1) {
cout << "0\n";
return;
}
for (int i = 0; i < n; i++) {
for (int j = i; j < n; j++) {
for (int k = 0; k < x; k++) {
dp[i][j][k] = n;
dpn[i][j][k] = n;
}
}
}
for (int i = 0; i < n; i++) {
for (int c = 0; c < x; c++) {
dp[i][i][c] = (a[i] != c);
dpn[i][i][c] = (a[i] == c);
}
}
for (int len = 2; len <= n; len++) {
for (int l = 0, r = len - 1; r < n; l++, r++) {
// don't paint [l, r]
for (int c = 0; c < x; c++) {
for (int i = l; i < r; i++) {
cmin(dp[l][r][c], dp[l][i][c] + dp[i + 1][r][c]);
cmin(dpn[l][r][c], dpn[l][i][c] + dpn[i + 1][r][c]);
}
}
// paint [l, r]
for (int c = 0; c < x; c++) {
if (c != a[l]) {
cmin(dpn[l][r][c], dpn[l + 1][r][c]);
}
if (c != a[r]) {
cmin(dpn[l][r][c], dpn[l][r - 1][c]);
}
if (c != a[l] || c != a[r]) {
cmin(dp[l][r][c], dpn[l][r][c] + 1);
}
}
if (a[l] == a[r]) {
int c = a[l];
cmin(dp[l][r][c], dp[l + 1][r][c]);
for (int i = 0; i < x; i++) {
if (i == c) continue;
cmin(dpn[l][r][c], dp[l][r][i]);
}
}
}
}
int ans = n;
for (int i = 0; i < x; i++) {
cmin(ans, dp[0][n - 1][i]);
}
cout << ans << '\n';
}
int main() {
int t = 1;
cin >> t;
while (t--) {
solve();
}
return 0;
}
还有神仙提交
用了 bitset 加速，看起来是没有保存所有的转移，但没充分看懂这里记录一下
https://codeforces.com/contest/1922/submission/242351751
#include<bits/stdc++.h>
#pragma GCC optimize("03")
using namespace std;
#define ll long long
#define fastio() ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL)
#define all(a) a.begin(),a.end()
#define endl "\n"
#define sp " "
#define pb push_back
#define mp make_pair
#define vecvec(type, name, n, m, value) vector<vector<type>> name(n + 1, vector<type> (m + 1, value))
void __print(int x) {cerr << x;}
void __print(long x) {cerr << x;}
void __print(long long x) {cerr << x;}
void __print(unsigned x) {cerr << x;}
void __print(unsigned long x) {cerr << x;}
void __print(unsigned long long x) {cerr << x;}
void __print(float x) {cerr << x;}
void __print(double x) {cerr << x;}
void __print(long double x) {cerr << x;}
void __print(char x) {cerr << '\'' << x << '\'';}
void __print(const char *x) {cerr << '\"' << x << '\"';}
void __print(const string &x) {cerr << '\"' << x << '\"';}
void __print(bool x) {cerr << (x ? "true" : "false");}
template<typename T, typename V>
void __print(const pair<T, V> &x) {cerr << '{'; __print(x.first); cerr << ','; __print(x.second); cerr << '}';}
template<typename T>
void __print(const T &x) {int f = 0; cerr << '{'; for (auto &i: x) cerr << (f++ ? "," : ""), __print(i); cerr << "}";}
void _print() {cerr << "]\n";}
template <typename T, typename... V>
void _print(T t, V... v) {__print(t); if (sizeof...(v)) cerr << ", "; _print(v...);}
#ifndef ONLINE_JUDGE
#define debug(x...) {cerr << "[" << #x << "] = ["; _print(x);}
#define reach cerr << "reached" << endl
#else
#define debug(x...)
#define reach
#endif
const int MOD = 1e9+7;
const int64_t inf = 0x3f3f3f3f, INF = 1e18, BIG_MOD = 489133282872437279;
/*--------------------------------------------------------------------------------------------------------------------------------------------------------------------------*/
// #define int int64_t
const int N = 120;
int n, x;
int a[N];
int dp[2][N][N]; // 0 => equal, 1 => exclude
bitset<N> opt[2][N][N];
int32_t main()
{
fastio();
int t;
cin >> t;
while(t --)
{
cin >> n >> x;
for(int i = 1; i <= n; i ++) cin >> a[i];
for(int l = 0; l <= n + 5; l ++)
for(int r = l; r <= n + 5; r ++)
for(int t = 0; t < 2; t ++)
{
opt[t][l][r].reset();
dp[t][l][r] = inf;
}
bitset<N> all;
for(int i = 1; i <= x; i ++) all.flip(i);
for(int i = 1; i <= n; i ++)
{
dp[0][i][i] = 0;
opt[0][i][i].flip(a[i]);
dp[1][i][i] = 0;
opt[1][i][i] = all;
opt[1][i][i].flip(a[i]);
}
for(int len = 2; len <= n; len ++)
{
for(int l = 1, r = len; r <= n; l ++, r ++)
{
for(int m = l; m < r; m ++) //combine dp[l][m] and dp[m + 1][r]
{
//dp[0][l][r]
{
for(int i = 0; i <= 1; i ++)
{
for(int j = 0; j <= 1; j ++)
{
auto comb = (opt[i][l][m] & opt[j][m + 1][r]);
if(comb.count())
{
int cost = dp[i][l][m] + dp[j][m + 1][r] + i + j;
if(cost < dp[0][l][r])
{
dp[0][l][r] = cost;
opt[0][l][r] = comb;
}
else if(cost == dp[0][l][r])
opt[0][l][r] |= comb;
}
}
}
}
// dp[1][l][r]
{
auto comb = (opt[1][l][m] & opt[1][m + 1][r]);
if(comb.count() == 0)
{
int cost = dp[1][l][m] + dp[1][m + 1][r] + 1;
if(cost < dp[1][l][r])
{
dp[1][l][r] = cost;
opt[1][l][r] = (opt[1][l][m] | opt[1][m + 1][r]);
}
else if(cost == dp[1][l][r])
opt[1][l][r] |= (opt[1][l][m] | opt[1][m + 1][r]);
}
else
{
int cost = dp[1][l][m] + dp[1][m + 1][r];
if(cost < dp[1][l][r])
{
dp[1][l][r] = cost;
opt[1][l][r] = comb;
}
else if(cost == dp[1][l][r])
opt[1][l][r] |= comb;
}
}
}
}
}
cout << min(dp[0][1][n], dp[1][1][n] + 1) << endl;
}
}
Next: [CF] B. Farmer John's Card Game - Codeforces Round 998 (Div. 3)