买了个域名怎么做网站/外链吧官网

有一排正数，玩家A和玩家B都可以看到。

每位玩家在拿走数字的时候，都只能从最左和最右的数中选择一个。

玩家A先拿，玩家B再拿，两人交替拿走所有的数字，

两人都力争自己拿到的数的总和比对方多。请返回最后获胜者的分数。

 

例如：

5,2,3,4

玩家A先拿，当前他只能拿走5或者4。

如果玩家A拿走5，那么剩下2，3，4。轮到玩家B，此时玩家B可以选择2或4中的一个，…

如果玩家A拿走4，那么剩下5，2，3。轮到玩家B，此时玩家B可以选择5或3中的一个，…

思路：

动态规划，设定两个状态，

分别为f（i，j）和 s（i，j）分别表示在 序列i..j 之间，先手能得到的最大数目以及后手计算后剩下的最大数目。

所以先手f（i，j） = max（arr[i]+s(i+1，j)，arr[j]+s(i，j-1)） 表示目的为求最大的情况

后手剩下的为  s（i,j）= min(f（i+1，j),f（i，j-1);  而后手玩家为了拿到更多，所以他会选择，留给对方最少的那种情况。

通过这种相互依赖，我们可以写出递归函数，并设定递归边界，

在先手情况下f（i，j），如果 i==j 表示只剩下最后一个，那么 就直接返回这个数。

 在后手情况下s（i，j），如果 i==j 表示只剩下最后一个，那么 就直接返回0。因为后手玩家已经取完了，所以留给先手玩家的就为0；

接着，通过画出依赖关系，我们可以发现f和s的相互关系，并且很多情况的递归都是重复计算的，所以这里就出现了无后效性的情况，即后面的计算都不会改变之前已经计算好的。就可以根据这个写出动态规划。

代码：

#include<iostream>
#include<stdio.h>
using namespace std;
int arr[1000] = {0}; int N;
//设置两个状态图 
int dps[1000][1000]={0};
int dpf[1000][1000]={0};int main() {scanf("%d",&N);for(int i=0;i<N;i++){scanf("%d",&arr[i]);}for (int j=0;j<N;j++){//先手状态初始化 dpf[j][j] = arr[j];for (int i = j-1;i>=0;i--){//先手状态和后手状态依次计算 dpf[i][j] = max(arr[i]+ dps[i+1][j],arr[j]+dps[i][j-1]);dps[i][j] = min(dpf[i+1][j],dpf[i][j-1]);}}printf("%d\n",dpf[0][N-1]);return 0;
}