题目描述

实数 $x_1,x_2,...,x_m$ 满足：

$$\begin{cases}-\dfrac1{\sqrt a}\le x_i\le \sqrt {a}\\ x_1+x_2+...+x_m=b\sqrt a\end{cases}$$

最大化目标函数

$$F(x_1,x_2,...,x_m)=x_1^p+x_2^p+...+x_m^p$$

其中 $m,p,a,b\in\mathbb Z$，且 $a>0$， $p$ 为正的偶数。

输入格式

输入由多组数据构成，每行一组数据，包含 $4$ 个整数 $m,p,a,b$。数据保证 $a>0$、 $p$ 为偶数，且存在一组实数 $x_1,x_2,...,x_m$ 满足题设条件。

输出格式

对于每组数据，输出一行一个整数，代表该组数据下目标函数 $F(x_1,x_2,...,x_m)$ 的最大值（四舍五入至最近的整数）。

数据范围

对于每组数据， $m\le 2000$， $p\le 12$。

输入样例

1997 12 3 -318
10 2 4 -1

输出样例

189548
6

题目分析

该问题属于带约束的优化问题，约束条件为线性约束，目标函数为非线性函数。根据目标函数的凸性，考虑采用调整法/凸优化的方法：

固定 $x_1,x_2,...,x_{m-2}$，设 $x_{m-1}+x_m=d$，则

$$F(x_1,x_2,...,x_m)=x_1^p+x_2^p+...+x_{m-2}^p+(d-x_m)^p+x_m^p\triangleq F(x_m)$$

则

$$F'(x_m)=px_m^{p-1}-p(d-x_m)^{p-1}$$

且

$$F''(x_m)=p(p-1)x_m^{p-2}+p(d-x_m)^{p-2}\geq 0$$

易见 $F'(x_m)$ 的唯一零点为 $\dfrac d2$，因此 $F(x_m)$ 在其定义域的边界上取得最值。

下证：当目标函数 $F(x_1,x_2,...,x_m)$ 取最大值时，至多有一个 $x_i\notin\{-\frac1{\sqrt a},\sqrt a\}$。

• 当 $m=1$ 时，命题平凡。
• 当 $m\ge 2$ 时，假设有不少于2个 $x_i\notin\{-\frac1{\sqrt a},\sqrt a\}$，不妨设 $x_i,x_j\notin\{-\frac1{\sqrt a},\sqrt a\}$，则保持 $x_i+x_j$ 不变的前提下将 $x_i$ 或 $x_j$ 调整至边界时 $F$ 更大，此时必有 $x_i'$ 或 $x_j'\in\{-\frac1{\sqrt a},\sqrt a\}$。

因此，可以枚举 $x_1,x_2,...,x_m$ 中 $\sqrt a$ 的数量：设 $x_1=x_2=...=x_k=\sqrt a$， $x_{k+1}=...=x_{m-1}=-\dfrac1{\sqrt a}$，则 $x_m=b\sqrt a-k\sqrt a+(m-k-1)\cdot\dfrac1{\sqrt a}$。若 $x_m\in[-\dfrac1{\sqrt a},\sqrt a]$，则计算当前的 $F(x_1,x_2,...,x_m)$，对所有 $k$ 取最大值即得 $F(x_1,x_2,...,x_m)$ 的全局最大值。

参考代码

#include <iostream>
#include <cmath>

using namespace std;

int main(){
	int m, p, a, b;
	double maxf = -1, f, bound;
	while (~scanf("%d %d %d %d", &m, &p, &a, &b)){
		maxf = 0;
		bound = sqrt((double) a);
		for (int i = 0; i < m; i++){
			double x = b * bound - i * bound - (m - i - 1) * (-1 / bound);
			if (x <= bound && x >= -1 / bound){
				f = i * pow(bound, p) + (m - i - 1) * pow(1 / bound, p) +pow(x, p);
				if (f > maxf) maxf = f;
			}
		}
		printf("%.0f\n", maxf);
	}
	return 0;	
}