Appoint description:
Description
The world is in danger! People really worry about climate change. Two largest research centres — Warmtown's and Freezetown's, have been doing active researches in this field for many years. In Warmtown's centre scientists believe
that the global warming is threateing the Earth. In Freezetown's center they believe that another Ice Age is expected on our planet.
that the global warming is threateing the Earth. In Freezetown's center they believe that another Ice Age is expected on our planet.
Such researches require enormous amounts of money, that is why Freezetown's and Warmtown's centres always apply for state grants. There is n billions zollars in the State budget, the size of the requested grant varies
from 1 to k billions. The Government realizes significance of the problem and fully pays all requested grants. If one of the research centres will get two grants in a row, the other will find it unfair and will give up researches. But then it can
be a big danger for Earth. So, it is possible to apply for grants one by one only. If there is no money in the budget then applications are not accepted any more. If there is not enough money in the budget to pay currently requested grant then the Minister
of Education and Science resigns in disgrace but first he gives all his m billions fortune to the centre which applied for that grant (money from budget is not taken in this case) and then grants are not given any more.
from 1 to k billions. The Government realizes significance of the problem and fully pays all requested grants. If one of the research centres will get two grants in a row, the other will find it unfair and will give up researches. But then it can
be a big danger for Earth. So, it is possible to apply for grants one by one only. If there is no money in the budget then applications are not accepted any more. If there is not enough money in the budget to pay currently requested grant then the Minister
of Education and Science resigns in disgrace but first he gives all his m billions fortune to the centre which applied for that grant (money from budget is not taken in this case) and then grants are not given any more.
Warmtown's and Freezetown's centres are swore enemies that is why each center is trying to get more money and to minimize the total amount of grants of the contender. The director of Warmtown's centre applied for grant first.
How much money will Warmtown's and Freezetown's centres get till payment stops? The budget is not used for paying other purposes in this period of time.
How much money will Warmtown's and Freezetown's centres get till payment stops? The budget is not used for paying other purposes in this period of time.
Input
The only line contains integers n, m and k (0 ≤ n ≤ 10 000; 0 ≤ m ≤ 1000; 1 ≤ k ≤ 100).
Output
Output total amounts of money that Warmtown's and Freezetown's centres got from Ministry respectively.
Sample Input
| input | output |
|---|---|
12 30 10 |
31 10 |
题意：有n元，和m元备用，每轮没人轮流取1~k元，当要取的值大于当前剩下的值，则把备用的m元给那个人，并且2个人都要使自己的值最大，并使总值尽量小
题解：这是一道博弈dp，由于2个人所要达到的状态是一样的，可以设n*2的dp状态，dp【i】【0】为取到状态i元的时候那个人所得的最大值，dp【i】【1】为取到状态i元的时候那个人的对手所得的最小值
#include<stdio.h>
#include<string.h>
#include<algorithm>
using namespace std;
int dp[10008][2];
int main()
{
int n,m,k,i,j;
while(scanf("%d%d%d",&n,&m,&k)>0)
{
memset(dp,0,sizeof(dp));
for(dp[k][0]=k,i=1;i<k;i++) dp[i][0]=m;
if(m<k) for(i=m+1;i<=k;i++) dp[i][0]=i;
for(i=k+1;i<=n;i++)
{
for(j=1;j<=k;j++)
{
if(i-j<0) continue;
if(dp[i][0]<dp[i-j][1]+j||(dp[i][0]==dp[i-j][1]+j&&dp[i][1]>dp[i-j][0]))
{
dp[i][0]=dp[i-j][1]+j;
dp[i][1]=dp[i-j][0];
}
}
}
printf("%d %d\n",dp[n][0],dp[n][1]);
}
return 0;
}