题解：CF1312E Array Shrinking

· · 题解

看到题解都是用的 O(n^3) 的区间 DP，蒟蒻在这里给出一种不需要区间 DP 且时间复杂度为 O(nv) 的做法。

有一个很经典的题是问 a 能够得到的最大的数是多少。

考虑定义 F(i, j) 代表 i 开始的区间要合成值 j 的所需要的区间的右端点 +1，也就是说 [i, F(i, j)) 这个区间可以合成 j，转移是类倍增的。但是这样不能够解决问题。

考虑定义 G(i) 代表考虑构成 [i, n] 的最小可能长度，转移为 G(i) \gets \min\{G(F(i,v)) + 1\}。

最终的答案即为 G(1)，代码非常短。

const int N = 500 + 5;
int F[N][1500];

signed main() {
    ios::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    int n; cin >> n;
    for(int i = 1, x; i <= n; i++) cin >> x, F[i][x] = i + 1;
    rep(v, 2, 1500 - 1) rep(i ,1, n) {
        auto &f = F[i][v], f1 = F[i][v - 1] ;
        if(f == 0 && f1 && f1 <= n + 1) f = F[f1][v - 1];
    }
    vector<int> G(n + 10, 1e9) ;
    G[n + 1] = 0;
    per(i, n, 1) rep(v, 1, 1500 - 1) {
        auto &f = F[i][v];
        if(F[i][v]) G[i] = min(G[i], G[F[i][v]] + 1);
    }
    cout << G[1] << '\n';
    return 0;
}