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

题意：你现在分数为a，对方分数为b，你比赛还有n分钟，每次进攻需要15分钟，现在你先进攻，每次进攻可以得1或2或3，对方每次进攻得一分，问超过对方分数有多少种打法

思路：因为情况太多要用__int64，很简单的dp，dp[n][m],n为第几次进攻，m为得分

#include <iostream>

#include<cstdio>

#include<cstring>

using namespace std;

int dir[]={1,2,3};

__int64 dp[40][120];

int main(int argc, char** argv) {

	int a,b,t,n,m,i,j,k,s;

	while(scanf("%d%d%d",&a,&b,&t)!=EOF){

		n=t/15;//

		m=n/2;// m场进攻

		s=n/2;//m场防守

		if(n%2)

			m++;//有多要多一场进攻

		memset(dp,0,sizeof(dp));

		dp[0][a]=1;//初始情况

		dp[1][a+1]=1;

		dp[1][a+2]=1;

		dp[1][a+3]=1;

		for(i=2;i<=m;i++)

			for(j=0;j<3;j++){

				for(k=a;k<=a+m*3;k++){

					if(dp[i-1][k]){

						dp[i][k+dir[j]]+=dp[i-1][k];//投球得分

					}

				}

			}

		__int64 sum=0;

		for(i=b+1+s;i<=a+m*3;i++)//多于对方分数的情况相加

			if(dp[m][i])

				sum+=dp[m][i];

		printf("%I64d\n",sum);

	}

	return 0;

}

巴特西

hdu 4504 威威猫系列故事——篮球梦_简单dp

最新文章

热门文章