B - Game of Sum dp1

本文主要是介绍B - Game of Sum dp1，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

题意：

区间DP，以前看过一些关于区间DP的题目，但是没有做过题目，没有反应过来这是区间DP得题目。说一下题意：

给定n个石头，每个石头有一个分数，现在小伙伴A和小伙伴B进行一个游戏，小伙伴A先手，每个人每次可以选择从头或从尾取k个石头，要求出如果两个人每次都按自己最好的情况去取，最后A大于B的最大分数差是多少。

思路：

区间DP的经典题目，采用dfs枚举一下，运用sump[i][j]表示i开头j结尾的分数，dp[i][j]表示取得值，运用记忆化搜索，标记一下，有结果值得直接返回即可，一开始M开大了，一直WA。详见代码：

#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;
#define INF 0x7f7f7f7f
const int M = 105;
int n;
int num[M],sum[M][M],dp[M][M],vis[M][M];
int dfs(int i,int j)
{int ans=-INF;if(i>j) return 0;if(vis[i][j]) return dp[i][j];vis[i][j] = 1;for(int k=1;k<=j-i+1;k++){ans = max(ans,sum[i][j]-min(dfs(i+k,j),dfs(i,j-k)));}return dp[i][j]=ans;
}int main()
{while(~scanf("%d",&n)){if(n==0) break;memset(dp,0,sizeof(dp));memset(vis,0,sizeof(vis));for(int i=0;i<n;i++){scanf("%d",&num[i]);}for(int i=0;i<n;i++){int cnt=0;for(int j=i;j<n;j++){cnt+=num[j];sum[i][j] = cnt; ///总和}}int aans = 2*dfs(0,n-1)-sum[0][n-1];  ///dfs(0, n-1) - (Sum[0][n-1] - dp(0, n-1)printf("%d\n",aans);}return 0;
}

这篇关于B - Game of Sum dp1的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---