标签：10 ch int void CF1572C Paint isdigit

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();
}

标签：10,ch,int,void,CF1572C,Paint,isdigit
From： https://www.cnblogs.com/DCH233/p/17249781.html