我觉得发学术板看的人应该会多一点。

给一篇题解帮助理解。

子问题就是说：

• 记 $S={(x,y)|x\ge 0,y\ge 0)}$，并给定 $k$。
• 设 $f(x)$ 表示在 $S$ 内选择恰好 $k$ 个点，使得他们的横坐标之和恰好为 $x$，此时纵坐标之和的最小值，其中 $x\ge 0$。
• 显然 $f(x)$ 单调不增，但是他并不是凸的，详见下面的例子：

当 $k=5$ 时，$f(0)=(0+1+2+3+4)=10$，$f(1)=(0+0+1+2+3)=6$，$f(2)=(0+1+0+1+2)=4$，$f(3)=(0+0+1+0+1)=2$，$f(4)=(0+0+1+0+1)=2$，$f(5)=(0+0+0+0+1)=1$

但是你可以发现一个贪心：对于 $f(i)$ 的最优决策，假设他是从 $f(i-1)$ 转移过来的。

考虑任意一个 $f(i-1)$ 的最优决策，记 $C_x$ 为横坐标为 $x$ 时放的点数之和，显然这些点的坐标分别为 $(x,0),(x,1)...(x,C_x-1)$，并且有：$\sum_x C_x\times x=i-1$。

当从 $i-1$ 推到 $i$ 时，我们假装只会改变 $O(1)$ 个元素。那么我们考虑将其中一个元素往上移。假设移动的元素的横坐标为 $x$，那么大概是选择其中 $y$ 最大的一个元素进行移动，即把 $(x,C_x)$ 移动到 $(x+1,C_{x+1}+1)$，那么在操作之后有：

那么贪心的想，我们大概是选择 $C_x-C_{x+1}$ 最大并且 $x$ 最小的一个，但是我不会证明正确性，有巨佬能帮帮吗QAQ。

或者提供另外的证明方式，只要能够说明 $(\sum x,\sum y)\times (p,q)$ 是凸的并且覆盖到了上面 $f$ 函数的每一个点（当两个点的取值相同时删除横坐标靠后的点）。

谢谢QWQ。

（另外，如果上述贪心成立，那么我们令 $g(y)$ 表示使纵坐标之和最小时候纵坐标之和等于 $y$，在满足这个条件下横坐标之和的最小值。那么 $g(y)$ 容易证明是一个下凸函数）