P7414 [USACO21FEB] Modern Art 3 G 题解

思路

考虑区间 DP。

设 \(f_{i, j}\) 表示要刷到 \([i, j]\) 这一段的目标需要的最小次数。

对于 \(f_{i, j}\)，

如果 \(color_i\) 与 \(color_j\) 相等，那么再子区间合并的时候就可以少刷一次，即 \(f_{i, j} = \min\limits_{k = i}^{j - 1}f_{i, k} + f_{k + 1, j} - 1\)。

否则 \(f_{i, j} = \min\limits_{k = i}^{j - 1}f_{i, k} + f_{k + 1, j}\)。

代码

#include <bits/stdc++.h>

using namespace std;

const int N = 310, INF = 0x3f3f3f3f;

int f[N][N];
int n, a[N];

int main() {
	ios::sync_with_stdio(false);
	cin.tie(nullptr);

    cin >> n;
    for (int i = 1; i <= n; i++) cin >> a[i];
    for (int len = 1; len <= n; len++) {
        for (int i = 1; i + len - 1 <= n; i++) {
            int j = i + len - 1;
            if (len == 1) f[i][j] = 1;
            else {
                f[i][j] = INF;
                for (int k = i; k < j; k++) {
                    if (a[i] == a[j]) f[i][j] = min(f[i][j], f[i][k] + f[k + 1][j] - 1);
                    else f[i][j] = min(f[i][j], f[i][k] + f[k + 1][j]);
                }
            }
        }
    }
    cout << f[1][n] << '\n';
	return 0;
}