欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页  >  IT编程

HDU - 4811 - Ball (思维)

程序员文章站 2022-07-02 15:19:48
题意: 给出一定数量的三种颜色的球,计算如何摆放得到值最大(有一定顺序) 有三种摆放方法 1、如果放的是第一个(桌子上原来没有),数值不变 2、如果在末尾追加一个,那么增加前面不同颜色的个数的值 3、如果在两个之间放置,那么增加两边不同颜色的个数的值 思路: b蓝 r红 y黄 三种摆放方法可以理解为 ......

题意:

给出一定数量的三种颜色的球,计算如何摆放得到值最大(有一定顺序)
有三种摆放方法
1、如果放的是第一个(桌子上原来没有),数值不变
2、如果在末尾追加一个,那么增加前面不同颜色的个数的值
3、如果在两个之间放置,那么增加两边不同颜色的个数的值

思路:

b蓝 r红 y黄
三种摆放方法可以理解为两种,2和3归为一种。
寻求最大值的话,一定是每次在中间放置球,这样得到的值更大

首先,如果每个球大于2个的话,就是说可以拿出部分球摆成以下这样情况
brybry,两边都有3种颜色,剩下的球全部放在yb之间,每次增加6

那么只需要计算 (总数-6)* 6 + 摆放6个时得到的分数
若有颜色不到2个,那么一开始两边摆的球的颜色数就会减少
设此时两边的颜色总数和为a,那么后面每个加入的球放中间都能得到a分

ans=(总的球数-先摆的球数)*a+b(b为先摆的过程中所获得的得分)

那么b怎么计算呢,在摆放最开始几个球的时候,会发现是一个等差数列,1,2,3...
所以我们直接用等差数列求和就可以得出b的值了
b=(0+先摆的球数-1)*先摆的球数/2

#include<iostream>

using namespace std;

typedef long long ll;

ll deal(ll x) {
    return x > 2 ? 2 : x;
}

int main() {
    ll a, b, c;
    while (~scanf("%lld %lld %lld", &a, &b, &c)) {
        ll index = deal(a) + deal(b) + deal(c);
        ll sum = a + b + c - index;
        ll ans = sum * index + index * (index - 1) / 2;
        printf("%lld\n", ans);
    }
    return 0;
}