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; }
上一篇: C++判断回文
推荐阅读
-
HDU - 3823 Prime Friend(欧拉筛+思维)
-
hdu 5671 Matrix(BC——思维题)
-
HDU6370(思维+搜索
-
HDU - 4811 - Ball (思维)
-
F - A Simple Game HDU - 1851----------------------思维(尼姆博弈+巴什博弈)
-
HDU-4705 Y(思维+dfs树)
-
HDU-1597 find the nth digit(思维)
-
Proving Equivalences【HDU-2767】【Tarjan缩点+度的思维】
-
HDU-1199 && ZOJ-2301---Color the Ball 区间染色-离散化非线段树做法
-
hdu6228 Tree (图论思维题)