[COCI2022-2023#4] Zrinka
题意
给定两个由 \(0,1\) 组成的序列。
\(0\) 只能填入偶数，\(1\) 只能填入奇数。
要求两个序列单调递增并且每个数最多使用一次。
求所用数最大值的最小值。
思路
动态规划。
定义 \(dp_{i,j}\) 表示序列 \(1\) 填到 \(i\)，序列 \(2\) 填到 \(j\) 的最小答案。
\[dp_{i,j}=\min \left \{ f(dp_{i-1,j}),f(dp_{i,j-1}) \} \right. \]\(f(x)\) 表示大于 \(x\) 第一个合法的数，具体条件取决于当前数是 \(0\) 还是 \(1\)。
答案为 \(dp_{n,m}\)。
代码
#include <bits/stdc++.h>
using namespace std;
const int N = 5005;
int n, m, dp[N][N], a[N], b[N];
int nxt(int x, int typ) {
if (typ == 0) {
if (x % 2 == 1) return x + 1;
else return x + 2;
} else {
if (x % 2 == 1) return x + 2;
else return x + 1;
}
}
int main() {
cin >> n;
for (int i = 1; i <= n; i ++) {
cin >> a[i];
}
cin >> m;
for (int i = 1; i <= m; i ++) {
cin >> b[i];
}
memset(dp, 0x3f, sizeof(dp));
dp[0][0] = 0;
for (int i = 0; i <= n; i ++) {
for (int j = 0; j <= m; j ++) {
if (i != 0) {
dp[i][j] = min(dp[i][j], nxt(dp[i - 1][j], a[i]));
}
if (j != 0) {
dp[i][j] = min(dp[i][j], nxt(dp[i][j - 1], b[j]));
}
}
}
cout << dp[n][m] << "\n";
return 0;
}