经验首页 前端设计 程序设计 Java相关 移动开发 数据库/运维 软件/图像 大数据/云计算 其他经验
当前位置:技术经验 » 程序设计 » C » 查看文章
HDU - 4811 - Ball (思维)
来源:cnblogs  作者:somliy  时间:2018/9/26 18:01:07  对本文有异议

题意:

给出一定数量的三种颜色的球,计算如何摆放得到值最大(有一定顺序)
有三种摆放方法
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

  1. #include<iostream>
  2. using namespace std;
  3. typedef long long ll;
  4. ll deal(ll x) {
  5. return x > 2 ? 2 : x;
  6. }
  7. int main() {
  8. ll a, b, c;
  9. while (~scanf("%lld %lld %lld", &a, &b, &c)) {
  10. ll index = deal(a) + deal(b) + deal(c);
  11. ll sum = a + b + c - index;
  12. ll ans = sum * index + index * (index - 1) / 2;
  13. printf("%lld\n", ans);
  14. }
  15. return 0;
  16. }
 友情链接:直通硅谷  点职佳  北美留学生论坛

本站QQ群:前端 618073944 | Java 606181507 | Python 626812652 | C/C++ 612253063 | 微信 634508462 | 苹果 692586424 | C#/.net 182808419 | PHP 305140648 | 运维 608723728

W3xue 的所有内容仅供测试,对任何法律问题及风险不承担任何责任。通过使用本站内容随之而来的风险与本站无关。
关于我们  |  意见建议  |  捐助我们  |  报错有奖  |  广告合作、友情链接(目前9元/月)请联系QQ:27243702 沸活量
皖ICP备17017327号-2 皖公网安备34020702000426号