C++卡片游戏

/* 蒜头君设计了一个双人游戏，在桌面上放置一排 n 张卡片，第 i 张卡片上有一个数字 a_i。 两个人轮流取走一张卡片，直至全部取完。注意每次只能取这一排卡片中的第一张或最后一张。最后取得卡片的数字和最高的玩家获胜。 蒜头君和花椰妹开始玩这个游戏。蒜头君先手，他可以使用任意策略。花椰妹计算能力有限， 所以她只单纯地使用贪心策略，即取两张卡片中数字较大的一张，如果两张卡片数字相同，则取第一张。 现在蒜头君想知道，在最佳策略下，他取得的分数会比花椰妹高多少？ 例如 4 张卡片，3 2 10 4。轮流取的卡片为 3, 4 ,10, 2 答案为 (3 + 10) - (4 + 2) = 7 区间dp，用递归去转移更直观一些 DP(l, r, p) : [l, r]表示剩余卡牌区间，p表示此时取卡片的玩家，p=0表示蒜头君，p=1表示花椰妹。 返回值为蒜头君得分和花椰妹的差值 p = 0 采用最佳策略，需要考虑子局面的分数：DP(l, r, 0) = max(DP(l, r - 1, 1) + a[r], DP(l + 1, r, 1) + a[l]); p = 1 采用贪心策略，a[l] < a[r], DP(l, r, 1) = DP(l, r - 1, 0) - a[r]; a[l] >= a[r], DP(l, r, 1) = DP(l - 1, r, 0) - a[l]; */ #include <iostream> using namespace std; const int maxn = 1005; int dp[maxn][maxn]; bool vis[maxn][maxn]; //记忆化处理，防止重复计算 int a[maxn], n; int DP(int l, int r, int p) { if (vis[l][r]) { return dp[l][r]; } if (l > r) { return 0; //如果说左边界 超出 右边界时 此时其实已经把牌给取走完了，所以对差值没有贡献 即为0 } vis[l][r] = 1; int res = 0; //保存差值 其实 可以不用声明此变量 因为dp这个二维数组 就是存放的区间差值 if (p == 0) { res = max(DP(l, r - 1, 1) + a[r], DP(l + 1, r, 1) + a[l]); //蒜头君对于差值的贡献 自然就是最佳选牌策略 } else { if (a[l] < a[r]) res = DP(l, r - 1, 0) - a[r];//花椰妹对于差值的贡献 是 利用贪心策略 让蒜头君的最佳策略 减去 当前最大那张牌 else res = DP(l + 1, r, 0) - a[l]; } return dp[l][r] = res; } int main() { cin >> n; for (int i = 1; i <= n; i++) { cin >> a[i]; } cout << DP(1, n, 0) << endl; //蒜头君先手权 return 0; }