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

· · 题解

看起来是 dp 的样子。

显然我们可以对 a[i] 同时取模 2，是没有影响的。则 a 就成了一个 01 序列。

发现：

  1. 每次交换一定是 0 和 1 交换（交换相同的显然没必要），进而想到交换操作是不会变化 a 数组中 1 的总量的。
  2. 每个位置最多被交换一次（交换多次显然不优，如 A \rightarrow B,B \rightarrow C,A \rightarrow C，没必要），即每个位置只有两种可能：变或不变。
  3. 发现代价很有特点，交换 (i,j) 代价为 c[i]+c[j]，我们不妨拆开考虑：令改变位置 i 的代价是 c[i]。

那么问题就换成了一个“放数”的问题，每个位置可以放 0 或 1，但不能超过序列中原本 1 的数量，这可以用序列上的 dp 模式解决。

设 dp[i][j][k] 表示前 i 个数，放了 j 个 1，且当前 s[i]=k 的最小代价。

考虑分类讨论当前位置是放 0 还是放 1 转移：

dp[i][j][k] \rightarrow dp[i + 1][j][k + j \bmod 2] \\ dp[i][j][k] \rightarrow dp[i + 1][j + 1][k + (j + 1) \bmod 2]

最后别忘了加上每次操作的代价，根据放的数是否和原数相同算即可。

时间复杂度 O(n^3)。

#include <bits/stdc++.h>
using namespace std;
const int inf = 2e9;

int n, a[505], c[505], dp[505][505][505];

signed main()
{
    ios :: sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr);
    int T; cin >> T;
    while(T --){
        cin >> n;
        int s = 0; // 记录1的总个数
        for(int i = 1; i <= n; i ++){
            cin >> a[i]; a[i] &= 1; s += a[i];
        }
        for(int i = 1; i <= n; i ++){
            cin >> c[i];
        }
        for(int i = 0; i <= n; i ++){
            for(int j = 0; j <= n; j ++) for(int k = 0; k <= n; k ++) dp[i][j][k] = inf;
        }
        dp[0][0][0] = 0;
        for(int i = 0; i <= n-1; i ++){
            for(int j = 0; j <= n; j ++){
                for(int k = 0; k <= n; k ++){
                    if(dp[i][j][k] == inf) continue;
                    dp[i+1][j][k+(j&1)] = min(dp[i+1][j][k+(j&1)], dp[i][j][k] + c[i+1]*(a[i+1]!=0)); // 放0
                    dp[i+1][j+1][k+(j+1&1)] = min(dp[i+1][j+1][k+(j+1&1)], dp[i][j][k] + c[i+1]*(a[i+1]!=1)); // 放1
                }
            }
        }
        for(int i = 0; i <= n; i ++){
            int ans = dp[n][s][i];
            cout << (ans == inf? -1 : ans) << " \n"[i == n];
        }
    }
    return 0;
}

警示后人：多测一定不要用 memset，按照输入的 n 清空，不然 T 到起飞！！！