首页 > 代码库 > HDU-4811 Ball 想法题

HDU-4811 Ball 想法题

有三种颜色的气球,把它们排成一排放在桌子上。

第一个气球不得分。

把一个气球放在末尾得到的分数是它以前气球的颜色种数

把一个气球放在中间得到的分数是它前边气球的颜色种数+后边的气球颜色种数。

求最高得分。

从条件可以推出当两边各放置一个同颜色气球时,此气球提供的分数已经饱和,所以先算出来都不到2的个数(分类是在太麻烦,不如手算),然后算出来有多少个气球是不需要考虑的*一个气球的得分,相加就好了。

#include <iostream>
#include <cmath>
#include <queue>
#include <cstdio>
#include <cstring>
#include <vector>
#include <iomanip>
#include <algorithm>
#define LL long long
using namespace std;
LL a[4];
LL f[3][3][3];
int main()
{
	int cnt;
	LL ans;
	f[0][0][0]=0,f[0][0][1]=0,f[0][0][2]=1,f[0][1][1]=1,f[0][1][2]=3,f[0][2][2]=6;
 	f[1][1][1]=3,f[1][1][2]=6,f[1][2][2]=10,f[2][2][2]=15;
	while(scanf("%I64d%I64d%I64d",&a[0],&a[1],&a[2])!=EOF)
	{
		cnt=0;
		for(int i=0;i<3;i++)
		{
			if(a[i]>2)
			{
				cnt+=a[i]-2;
				a[i]=2;
			}
		}
		sort(a,a+3);
		LL p=a[0]+a[1]+a[2];
		ans=f[a[0]][a[1]][a[2]]+cnt*p;
		printf("%I64d\n",ans);
	}
	return 0;
}


HDU-4811 Ball 想法题