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

本文主要是介绍腾迅马拉松（〇）解题报告，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

                                     腾迅马拉松解体报告

 

    腾迅的第一场比赛主要是以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;
}

 

  

 

这篇关于腾迅马拉松（〇）解题报告的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---