郑州企业建设网站技术,建设网站挣钱,网站页面排版,地域文化创意产网站建设规则资源限制
内存限制#xff1a;256.0MB C/C时间限制#xff1a;1.0s Java时间限制#xff1a;3.0s Python时间限制#xff1a;5.0s
问题描述 逗志芃又一次面临了危机。逗志芃的妹子是个聪明绝顶的人#xff0c;相比之下逗志芃就很菜了。现在她妹子要和他玩一个游戏…资源限制
内存限制256.0MB C/C时间限制1.0s Java时间限制3.0s Python时间限制5.0s
问题描述 逗志芃又一次面临了危机。逗志芃的妹子是个聪明绝顶的人相比之下逗志芃就很菜了。现在她妹子要和他玩一个游戏这个游戏是这样的一共有n个数n是偶数写成一行然后两个人轮流取数每次只能从最前面或者最后面取走一个数全部取完则游戏结束之后每个人取走的数的和就是每个人的得分。由于逗志芃妹子很厉害但他又不想输所以只能找到你了你要告诉他最多可以得到多少分。注意妹子智商是maxlongint所以是不会犯错的每次的策略必然最优而且逗志芃是先手
输入格式 第一行一个数n表示有n个数。 第二行就是进行游戏的n个数。
输出格式 一个数最高得分
样例输入
2 10 20
样例输出
20
数据规模和约定 例0n,m1000,每个数不超过10000 。
#includeiostream
using namespace std;
const int N10e310;
int data[N];
int n;
int ans[N][N];
int main(){scanf(%d,n);for(int i0;in;i){scanf(%d,data[i]);}for(int Ln-1;L0;L--){for(int RL;Rn-1;R){if(LR){//初始状态 ans[L][R]0;}else if((L-R1)%20){//剩偶数个接下来一定是逗志芃拿数 ans[L][R]max(ans[L1][R]data[L],ans[L][R-1]data[R]);}else{//剩奇数个妹妹拿因为妹妹一定挑大的拿因此逗志芃的分数只能取小的那个 ans[L][R]min(ans[L1][R],ans[L][R-1]);}}} printf(%d\n,ans[0][n-1]);
} 思路动态规划。设ans[L][R]为在L~R范围内逗能获得的最高分。因为逗要获得最高分因此
ans[L][R]max(ans[L1][R]data[L],ans[L][R-1]data[R]); 轮到妹妹时妹妹也得取最大因此逗
ans[L][R]min(ans[L1][R],ans[L][R-1]);
以下是初始化的表格
可以举个例子来理解当只有两个数的时候(data[L]和data[R]要么取左边要么取右边ans[L][R]max(data[L],data[R])ans[L1][R]自然为0。这里L1R 接下来就是用双层for循环来填表。
