POJ-3066-Maximum解题思路

Let x1, x2, ..., xm be real numbers satisfying the following conditions:
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)