题解：P10715 【MX-X1-T3】「KDOI-05」简单的序列问题

cancan123456 · 2024-07-07 22:26:36 · 题解

首先将 a_i 变为 a_i\bmod 2，注意到我们不会交换两个相同的 a_i，只会交换 0 和 1，且同一个位置不会被交换两次。

因此考虑将一次交换看成两次切换：0\to1,1\to0，且将 a_i 切换需要 c_i 的代价。

容易发现如果 a_i 中 1 的数量如果与操作后 a_i' 中 1 的数量相同，则总可以构造出一种交换方案能够将 a_i 变为 a_i'，因此这种考虑是符合题意的。

现在设计 DP 状态：f_{i,j,k} 表示考虑了 a 长度为 i 的前缀，已经得到了 j 个 1，且前缀和序列 b 的前 i 项有 k 个 1 的最小花费。

初始状态显然为 f_{0,0,0}=0，其余状态全部为正无穷。

考虑从 f_{i,j,k} 转移，设操作后 a_{i+1}'=l，其中 0\le l\le1，则有转移：

求答案时，需要保证 a_i' 中的 1 数量等于 a 中的 1 数量 t，因此答案为 f_{n,t,S}，输出即可。

时间复杂度为 O(n^3)，可以通过此题，以下为赛时代码。

#include <cstdio>
using namespace std;
const int N = 505;
int a[N], c[N], f[N][N][N];
int min(int a, int b) {
    return a < b ? a : b;
}
int main() {
    int T;
    scanf("%d", &T);
    for (int n; T != 0; T--) {
        scanf("%d", &n);
        int cnt = 0;
        for (int i = 1; i <= n; i++) {
            scanf("%d", &a[i]);
            a[i] %= 2;
            cnt += a[i];
        }
        for (int i = 1; i <= n; i++) {
            scanf("%d", &c[i]);
        }
        for (int i = 0; i <= n; i++) {
            for (int j = 0; j <= n; j++) {
                for (int k = 0; k <= n; k++) {
                    f[i][j][k] = 0x3f3f3f3f;
                }
            }
        }
        // f[i][j][k] 为前 i 个数中 a[x] = 1 有 j 个，b 中 1 的个数为 k 的最小代价.
        f[0][0][0] = 0;
        for (int i = 0; i < n; i++) {
            for (int j = 0; j <= n; j++) {
                for (int k = 0; k <= n; k++) {
                    if (f[i][j][k] != 0x3f3f3f3f) {
                        for (int l = 0; l <= 1; l++) {
                            int & to = f[i + 1][j + l][k + (j + l) % 2];
                            to = min(to, f[i][j][k] + c[i + 1] * (a[i + 1] ^ l));
                        }
                    }
                }
            }
        }
        for (int i = 0; i <= n; i++) {
            if (f[n][cnt][i] != 0x3f3f3f3f) {
                printf("%d ", f[n][cnt][i]);
            } else {
                printf("-1 ");
            }
        }
        printf("\n");
    }
    return 0;
}