P2375 [NOI2014] 动物园AC代码

以下是一份P2375 [NOI2014] 动物园的AC代码，使用的是记忆化搜索实现：

#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]的值即可。

希望对你有所帮助！