P2375 [NOI2014] 动物园

P2375 [NOI2014] 动物园是一道经典的动态规划题目，以下是该题的详细题意和解题思路。

【题意描述】

有两个长度为 $n$ 的整数序列 $a$ 和 $b$，你需要从这两个序列中各选出一些数，使得这些数构成一个新的序列 $c$。其中，$c$ 序列中的元素必须在原序列中严格递增。每个元素都有一个价值，你的任务是选出的元素的总价值最大。

【解题思路】

这是一道经典的动态规划题目，可以采用记忆化搜索的方法解决，也可以采用递推的方法解决。

记忆化搜索的代码如下：

#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;

const int MAXN = 1005;
int dp[MAXN][MAXN], a[MAXN], b[MAXN], n;

int dfs(int x, int y) {
    if (dp[x][y] != -1) return dp[x][y];
    if (x == n || y == n) return 0;
    int res = max(dfs(x + 1, y), dfs(x + 1, y + 1));
    if (a[x] > b[y]) {
        res = max(res, dfs(x, y + 1) + b[y]);
    }
    return dp[x][y] = res;
}

int main() {
    scanf("%d", &n);
    for (int i = 0; i < n; i++)
        scanf("%d", &a[i]);
    for (int i = 0; i < n; i++)
        scanf("%d", &b[i]);
    memset(dp, -1, sizeof(dp));
    printf("%d\n", dfs(0, 0));
    return 0;
}

其中，dp[i][j]表示选到a数组中第i个元素和b数组中第j个元素时的最大价值，-1表示未计算过。dfs(x,y)表示选到a数组中第x个元素和b数组中第y个元素时的最大价值，如果dp[x][y]已经计算过，则直接返回dp[x][y]的值。如果x==n或者y==n，表示已经遍历完一个数组，直接返回0。然后就是状态转移方程了，如果a[x] > b[y]，则可以尝试选b[y]，递归调用dfs(x, y+1)计算以后的最大价值。否则，只能继续遍历数组a，递归调用dfs(x+1, y)计算最大价值。最后，返回dp[0][0]的值即可。

递推的代码如下：

#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;

const int MAXN = 1005;
int dp[MAXN][MAXN], a[MAXN], b[MAXN], n;

int main() {
    scanf("%d", &n);
    for (int i = 0; i < n; i++)
        scanf("%d", &a[i]);
    for (int i = 0; i < n; i++)
        scanf("%d", &b[i]);
    for (int i = n - 1; i >= 0; i--) {
        for (int j = n - 1; j >= 0; j--) {
            dp[i][j] = max(dp[i + 1][j], dp[i + 1][j + 1]);
            if (a[i] > b[j]) {
                dp[i][j] = max(dp[i][j], dp[i][j + 1] + b[j]);
            }
        }
    }
    printf("%d\n", dp[0][0]);
    return 0;
}

其中，dp[i][j]表示选到a数组中第i个元素和b数组中第j个元素时的最大价值。从后往前遍历数组a和数组b，依次计算dp[i][j]的值。状态转移方程和记忆化搜索的方法是一样的。

【参考链接】

P2375 [NOI2014] 动物园：https://www.luogu.com.cn/problem/P2375