腾迅马拉松（〇）解题报告

腾迅马拉松解体报告

腾迅的第一场比赛主要是以DP为主。所以，你会看到是各种的DP的出现。虽然，题目不是很难，但是坑特多，一不注意，就会让你wrong的满屏都是。所以，要特别的细心的读题。

威威猫系列故事——篮球梦

题目链接:Click Here~

题目分析:

这道题目还是一道DP，但是，这是一个考查你对DP思想的理解。即，你要懂得动态规划的本质是什么。

思路分析：

这道题可以从动态规划的本质出发解决问题。即，每一个状态都可以从前面的状态推出。这题也是运用了这个思想。因此，可以推出转移方程式，但是这个状态有三个，因为以前的最优子结构是选或者不选，而这道题是肯定会选，但是有三种情况可以选，而每种情况又有着不同的结果。所以，下面就给出总的动态转移方程式：

1、dp[i][j] += dp[i-1][j-1];(j > 1)

2、dp[i][j] += dp[i-1][j-2];(j > 2)

3、dp[i][j] += dp[i-1][j-3];(j > 3)

这三个方程式要怎么理解呢？

我们还是要从算法的本质出发。即，我刚才一直强调的动态规划的本质，可以从上一个状态转移到下一个状态。但是，本题不需要动态规划的另一个本质，即，最优子结构。

还是说回本题。即，我们考虑当前的这场比赛，他是处于何种状态呢？显然他是有上一场结果传递下来的。所以，我们就可以假设，当前的状态dp[i][j] = dp[i-1][j-1]表示该次进攻得一分，而继承上次的情况。一下两个方程都是一样的意义。就不再解释了。

#include <iostream>
#include <algorithm>
#include <cstdio>
#include <cstring>
using namespace std;

typedef __int64 LL;
const int N = 80;
const int M = 25;
__int64 dp[M][N];
void Init()
{
    dp[1][1]=dp[1][2]=dp[1][3]=1;
    for(int i = 2;i < M;++i)
      for(int j = 1;j <= 3*i;++j){
         if(j > 1)
           dp[i][j] = dp[i-1][j-1];
         if(j > 2)
           dp[i][j] += dp[i-1][j-2];
         if(j > 3)
           dp[i][j] += dp[i-1][j-3];
      }
}
int main()
{
    Init();
    int a,b,t;
    while(~scanf("%d%d%d",&a,&b,&t))
    {
        int n = t/15; //总场数
        b += n/2;     //B的最后终分数
        n = n - n/2;   //A的剩余场数
        a = b - a;      //A必需要得到的最小分数
        if(!n){
           if(a >= 0){
              printf("0\n");
           }else
           {
               printf("1\n");  //什么都无需做就可以赢
           }
        }else
        {
            LL res = 0;
            if(a > 0)a++;       //必需要至少赢一场，不能平手
            if(a < 0) a = 0;    //肯定会赢得情况
            for(int i = a;i <= 3*n;++i)
              res += dp[n][i];
            printf("%I64d\n",res);
        }
    }
    return 0;
}