題目大意:有三種顏色的球若干,每次向桌子上放一個球,保證是一條序列,每次放球的得分為當前放入序列的球的前面有多少種不同的顏色a,後面的有多少種不同的顏色b,a+b。問說給定球的數量後,最大得分為多少。
解題思路:因為放球順序是自己定的,所以我們可以盡量早得構造一個序列,使得後面放入球的得分均保持在峰值。那麼求峰值就要根據球的數量來決定。我們叫得分為峰值的求為最高得分球,它們有很多個。對於一種顏色來說:0個,表示不能為在最高得分球的左邊和右邊,換句話來說,就是不能創造得分;1個,要麼在左要麼在右,創造一個得分;2個左右各一,創造兩個得分;2個以上,一邊有兩個沒有意義,所以還是兩個得分。
於是峰值即被求出來了,剩下的就簡單多了。
#include
#include
#include
#include
using namespace std;
typedef long long ll;
inline ll cal (ll u) {
if (u <= 2)
return u;
else
return 2;
}
int main () {
ll R, Y, B;
while (cin >> R >> Y >> B) {
ll h = cal(R) + cal(Y) + cal(B);
ll n = R + Y + B;
ll ans = 0;
for (ll i = 0; i < n && i < h; i++)
ans += i;
if (n > h)
ans += h * (n-h);;
cout << ans << endl;
}
return 0;
}