Voracious Steve
题目连接:
http://codeforces.com/gym/100231/attachments
Description
有两个人在玩一个游戏
有一个盆子里面有n个甜甜圈,A先开始,他可以抓[1,min(m,n)]颗甜甜圈,然后B开始,同样,可以抓[1,min(n,m)]个甜甜圈
谁抓完的,就可以把自己抓的吃完,然后另外一个人就把他的甜甜圈扔进去,然后由失败的那个人开始
问你第一个人最多能吃到多少个甜甜圈
Input
2个整数 n,m
表示一开始有n个甜甜圈,一次最多抓m个
Output
输出第一个人最多吃多少个甜甜圈
Sample Input
5 3
Sample Output
2
Hint
题意
题解:
记忆化搜索,dp[n][x][y]表示中间有n个甜甜圈,第一个人有x个,第二个人有y个的最优值
然后一直搜下去就好了
代码
#include<bits/stdc++.h>
using namespace std;
int dp[105][105][105];
int n,m;
int dfs(int n,int x,int y)//还有n个,我身上有x个,他身上有y个我能吃的最大值
{
if(dp[n][x][y]>=0)return dp[n][x][y];
for(int i=1;i<=m&&i<=n;i++)
{
int sp = n+x+y;
if(i==n)sp-=dfs(y,0,0);
else sp-=dfs(n-i,y,x+i);
dp[n][x][y]=max(dp[n][x][y],sp);
}
return dp[n][x][y];
}
int main()
{
memset(dp,-1,sizeof(dp));
scanf("%d%d",&n,&m);
dp[0][0][0]=0;
cout<<dfs(n,0,0)<<endl;
}