题解：P9173 [COCI 2022/2023 #4] Zrinka

Eric1030 · 2025-02-08 10:41:02 · 题解

题目传送门

这道题是一道运用到了多维 DP 的题目。

那么我们来看一下状态的定义。f[i][j] 是第一个数组填了前 i 个数字，第二个数组填了前 j 个数字，所得的最大数字的最小值。

在看状态转移方程之前我们要定义一个函数 ntx(x,y)，它表示最小的大于 x 且 \bmod 2 余数为 y 的数。

接下来我们来看一下状态转移方程。

接下来就是边界和初始化。我们要把 f[0][0] 设为 0，其余位置为无穷大。

但为什么要设为无穷大呢？因为要求最大的最小，其中用到了求最小值函数，如果设为 0 或无穷小，那么答案就是 0 或无穷小了。

最后就是输出答案 f[n][m] 了。

AC 代码

#include <bits/stdc++.h>
using namespace std;
int n, m, a[5005], b[5005], f[5005][5005];
const int inf = 1e9;
int ntx(int x, int y)
{
    for (int i = x + 1;;i++)
    {
        if (i % 2 == y)
        {
            return i;//返回最小的大于x且%2余数为y的数
        }
    }
}
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];
    }
    for (int i = 0;i <= n;i++)
    {
        for (int j = 0;j <= m;j++)
        {
            if (i == 0 && j == 0)//a数组1个都没填，b数组也1个都没填的情况不考虑了
            {
                continue;
            }
            f[i][j] = inf;//设为无穷大
            if (i >= 1)//避免RE
            {
                f[i][j] = min(ntx(f[i - 1][j], a[i]), f[i][j]);//填数
            }
            if (j >= 1)//同上，但两种情况要分开考虑
            {
                f[i][j] = min(ntx(f[i][j - 1], b[j]), f[i][j]);//填数
            }
        }
    }
    cout << f[n][m];//输出结果
    return 0;//结束！
}