学步园

昨天做比赛的时候状态确实不太好，而且之前的dp题基本都没做过，直接就扔给WQJ去想了，现在做DP的时候没怎么有思路，昨天做这题的时候没什么想法，后来好甜说是背包方案数，昨天晚上睡觉的时候想了一下好像确实挺简单的，今天敲过去了。就是算出来自己的决策有多少个阶段，每个阶段都有三种决策，1，2，3中的一种。所以状态转移方程也就很好写了if(dp[i-1][j]){dp[i][j+1]+=dp[i-1][j],dp[i][j+2]+=dp[i-1][j],dp[i][j+3]+=dp[i-1][j]}，最后找答案的时候算一下能赢的分数有哪些累加起来即可。第一次因为没用long
longWA了一次，第二次就过了。

#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;
long long dp[25][205];
int main()
{
    int a,b,t;
    while(scanf("%d%d%d",&a,&b,&t)!=EOF)
    {
        memset(dp,0,sizeof(dp));
        int turn=t/15,tot=turn/2+(turn&1);
        dp[0][0]=1;
        for(int i=1;i<=tot;i++)
        {
            for(int j=i-1;j<=(i-1)*3;j++)
            {
                if(dp[i-1][j])
                {
                    dp[i][j+1]+=dp[i-1][j];
                    dp[i][j+2]+=dp[i-1][j];
                    dp[i][j+3]+=dp[i-1][j];
                }
            }
        }
        long long ans=0;
        for(int i=max(tot,b-a+turn-tot+1);i<=tot*3;i++)
            ans+=dp[tot][i];
        cout<<ans<<endl;
    }
}