Codeforces Gym 100231G Voracious Steve 記憶化搜尋

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