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

看起来是 dp 的样子。

显然我们可以对

a[i]

同时取模

2

，是没有影响的。则

a

就成了一个 01 序列。

发现：

每次交换一定是 $0$ 和 $1$ 交换（交换相同的显然没必要），进而想到交换操作是不会变化 $a$ 数组中 $1$ 的总量的。
每个位置最多被交换一次（交换多次显然不优，如 $A \rightarrow B,B \rightarrow C,A \rightarrow C$ ，没必要），即每个位置只有两种可能：变或不变。
发现代价很有特点，交换 $(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)

。

CPP

#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 到起飞！！！

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

文章操作

相关推荐

评论

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