CF1927G Paint Charges 题解

wxzzzz · 2024-02-09 23:28:00 · 题解

思路

DP。

令 f_i 表示将 1\sim i 染色的最小代价。

考虑分类讨论答案。

1. 将 [i-a_i+1,i] 染色。代价为 \displaystyle\min_{j=i-a_i+1}^i f_{j-1}+1。

2. 将 [j,j+a_j-1]\ (j+a_j-1\ge i) 染色。代价为 \displaystyle\min_{j=1}^{i-1}[j+a_j-1\ge i]f_{j-1}+1。

但仅仅这样转移会有遗漏。

显然可以将 [k-a_k+1,k]\ (k>j) 和 [j,j+a_j-1]\ (j+a_j-1\ge i) 染色，从而使 [k-a_k+1,i] 被染色。

因此，在转移完 f_i 还要考虑将 [i,i+a_i-1] 染色后在 i+1\sim i+a_i-1 中选择一个 j，将 [j-a_j+1,j] 染色的最小代价。

具体转移详见代码。

代码

#include <bits/stdc++.h>
using namespace std;
int t, n, a[1005], f[1005];
int main() {
    cin >> t;

    while (t--) {
        memset(f, 0x3f, sizeof f);
        cin >> n;

        for (int i = 1; i <= n; i++)
            cin >> a[i];

        f[0] = 0;

        for (int i = 1, k, minn; i <= n; i++) {
            for (int j = max(i - a[i] + 1, 0); j <= i; j++)
                f[i] = min(f[i], f[j - 1] + 1);

            for (int j = 1; j < i; j++)
                if (j + a[j] - 1 >= i)
                    f[i] = min(f[i], f[j - 1] + 1);

            k = i - 1, minn = f[i - 1];

            for (int j = i + 1; j <= min(i + a[i] - 1, n); j++) {
                while (k > max(j - a[j], 0))
                    minn = min(minn, f[--k]);

                f[j] = min(f[j], minn + 2);
            }
        }

        cout << f[n] << '\n';
    }

    return 0;
}