Codeforces Gym 100231G Voracious Steve 记忆化搜索

时间:2023-03-21 16:24:01

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;
}