HDU 4811 Ball -2013 ICPC南京区域现场赛

时间:2021-12-17 16:22:32

题目链接

题意:三种颜色的球,现给定三种球的数目,每次取其中一个放到桌子上,排成一条线,每次放的位置任意,问得到的最大得分。

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

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

题解:由题意可知当三种颜色气球都大于等于2的时候是最好的情况,先一种颜色取两个得15分,然后把剩下的球全都放到中间即可,每次分数+6,题目中的样例就是这样的。当存在一种球的颜色小于2的时候我们分类讨论可以发现 0 1 1 和  0 0 2 的解是相同的,1 1 1 和 0 1 2 和 0 0 3 的解是相同的,后面都是 3*(3-1)/2 。我们把这个称之为底,每种颜色的球最多可以取两个加到底当中,再加上除去底之外的数*底即可。经过分析一个max一个min我们就可以得到结果了。

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int main()
{
ll data[];
while(scanf("%lld%lld%lld",&data[],&data[],&data[])!=EOF)
{
sort(data,data+);
ll sum1=min(data[],2LL)+min(data[],2LL)+min(data[],2LL);
ll sum2=data[]+data[]+data[]-sum1;
printf("%lld\n",sum1*(sum1-)/+sum1*sum2);
}
return ;
}