POJ-3066-Maximum解题思路

POJ-3066-Maximum解题思路

来源: | 浏览: 1594 | 评论: 1 发表时间: 2015-06-06 20:18:14

Let x1, x2, ..., xm be real numbers satisfying the following conditions: POJ - 3066
for some integers a and b (a > 0).
Determine the maximum value of x1^p + x2^p + … + xm^p for some even positive integer p.



Input

Each input line contains four integers: m, p, a, b (m <= 2000, p <= 12, p is even). Input is correct, i.e. for each input numbers there exists x1, x2, …, xm satisfying the given conditions.


Output

For each input line print one number – the maximum value of expression, given above. The answer must be rounded to the nearest integer.


Sample Input
Sample Output
解题思路

比较简单的贪心算法,由于p是偶数,所以尽量让所取的数字靠近a条件的两个极值,可以先全使用最小值填充(贪心),如果超过了b条件,减少最小值的数量(回溯),增加最大值的数量,如果回溯后的剩余值不够放下一个最大值,就用减法得出一个可满足条件b的值即可。


AC代码(0ms)


相关文章
  • 声明: 评论属于其发表者所有,不代表本站的观点和立场.
  • 路人甲 回复该留言 时间: 2015-11-02 11:22:52

    这都行

已有 1 位网友发表了一针见血的评论,你还等什么?
  • 昵称: *
  • 邮箱:
  • 网址:
  • 记住我的信息
  • Color
  • Red
  • Blue
  • Code
  • bash
  • cpp
  • css
  • java
  • js
  • perl
  • php
  • python
  • ruby
  • sql
  • xml








最新评论