CD91 排成一条线的纸牌博弈问题

本文主要是介绍CD91 排成一条线的纸牌博弈问题，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

题目

• 考查点：区间DP 博弈
• 题目：排成一条线的纸牌博弈问题
• 思路：两个数组，f表示先手的最大值s表示后手的最大值，最后求两个值的最大值。详情参考左程云的面试指南书籍。

代码

• 时间复杂度$O(n^2)$

#include <bits/stdc++.h>
using namespace std;
const int N = 5010;
int a[N], f[N][N], s[N][N];
int main(){int n;cin>>n;for(int i = 1; i <= n; i++) cin>>a[i];for(int len = 1; len <= n; len++){for(int i = 1; i + len - 1 <= n; i++){int j = i + len - 1;f[i][j] = max(a[i] + s[i+1][j], a[j] + s[i][j-1]);s[i][j] = min(f[i+1][j], f[i][j-1]);}}cout<<max(f[1][n], s[1][n])<<endl;
} 

这篇关于CD91 排成一条线的纸牌博弈问题的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---