学步园

题解：两个公司从教育部轮流申请资金，如果库中钱充足的话那么就会拨给这个公司，如果一旦库中没有钱那么停止，如果申请的钱多余库中的那么教育部长会

         把手中的m元钱给他之后申请结束，开始库中有n元钱，每个公司每次申请资金的范围是[1 , k]，问先手的公司最多能得到多少钱，在得到最多钱的情况下

         能让对手得到最少的钱数。

题解：开始是博弈的想法，枚举每个人决策的平衡态，莫名其妙的过了，队友搞了dp，找到一组反例证明我的博弈想法是有错误的，dp应该是正解。

          dp[ i ][ 0 ]代表的是当前剩余 i 元钱先手申请到的最多的钱，dp[ i ][ 1 ]代表剩余 i 元钱先手得到的最多钱时对手得到的最少的钱，转移方程具体见代码。

Sure原创，转载请注明出处

#include <iostream>
#include <cstdio>
#include <memory.h>
#define MAX(a , b) ((a) > (b) ? (a) : (b))
using namespace std;
const int maxn = 10002;
int dp[maxn][2];
int m,n,k;

void solve()
{
    memset(dp,0,sizeof(dp));
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=k;j++)
        {
            if(j <= i)
            {
                if(dp[i-j][1] + j > dp[i][0] || (dp[i-j][1] + j == dp[i][0] && dp[i][1] > dp[i-j][0]))
                {
                    dp[i][0] = dp[i-j][1] + j;
                    dp[i][1] = dp[i-j][0];
                }
            }
            else
            {
                if(dp[i][0] < m || (dp[i][0] == m && dp[i][1] > 0))
                {
                    dp[i][0] = m;
                    dp[i][1] = 0;
                }
                break;
            }
        }
    }
    printf("%d %d\n",dp[n][0],dp[n][1]);
    return;
}

int main()
{
    while(~scanf("%d %d %d",&n,&m,&k))
    {
        solve();
    }
    return 0;
}