AtCoder-ABC275F Erase Subarrays

Table of Contents

AtCoder-ABC275F Erase Subarrays #

题目大意 #

给定 $n, m$ 和长度为 $n$ 的整数数组 $a$ . 每次操作中, 你可以删除数组 $a$ 中的一个非空连续子数组. 对于 $x = 1, 2, \dots ,m$ , 输出使得剩余数组元素之和为 $x$ 的最少操作次数. 如果无法使 $a$ 的剩余数组元素之和等于 $x$ , 则输出 $-1$ .

Solution 1 #

定义 $dp[i][j][k]$ 为数组 $a_0, a_1, …, a_i$ 中删除连续非空子数组使得剩余元素和为 $j$ , 且是否删除了 $a_i$ 的最少操作次数, 其中 $k = 0$ 代表保留 $a_i$ , $k = 1$ 代表删除 $a_i$ . 有: $$ \begin{cases} dp[i][j][0] = min(dp[0][j - a_i][1], dp[0][j - a_i][0]);\ dp[1][j][1] = min(dp[0][j][1], dp[0][j][0] + 1);\end{cases} $$ 对于 $x$ , 答案是 $min(dp[n - 1][x][0], dp[n - 1][x][1])$ .

代码如下:

#include "bits/stdc++.h"

using namespace std;

int main() {
    int n, m;
    cin >> n >> m;
    int a[n];
    for (int i = 0; i < n; i++) {
        cin >> a[i];
    }
    int dp[2][3001][2];
    for (int j = 0; j <= m; j++) {
        for (int k = 0; k <= 1; k++) {
            dp[0][j][k] = 1e9;
        }
    }
    dp[0][a[0]][0] = 0;
    dp[0][0][1] = 1;
    for (int i = 1; i < n; i++) {
        for (int j = 0; j <= m; j++) {
            dp[1][j][0] =
                j >= a[i] ? min(dp[0][j - a[i]][1], dp[0][j - a[i]][0]) : 1e9;
            dp[1][j][1] = min(dp[0][j][1], dp[0][j][0] + 1);
        }
        for (int j = 0; j <= m; j++) {
            dp[0][j][0] = dp[1][j][0];
            dp[0][j][1] = dp[1][j][1];
        }
    }
    for (int j = 1; j <= m; j++) {
        int res = min(dp[0][j][0], dp[0][j][1]);
        cout << (res >= 1e9 ? -1 : res) << endl;
    }
    return 0;
}