题解 UVA12589 【学习向量 Learning Vector】

解法： 贪心+dp/记忆化搜索

Step 1. 贪心

首先可以说明，向量形成的图形一定为凸。否则一定可以对那对凹下去的边作平行四边形并平移过去，从而增大面积。

所以对开始所给的边按极角排序，从而消除选择顺序给答案带来的影响。

Step 2. 推式子

我们可以发现计算新形成的梯形面积由左右的高和该向量的横坐标决定，而后者给出。所以记录的条件一定有累计高度。另外题目所要求的$K$也必须记录（不然你怎么得到答案？）。

由于消除了选择顺序带来的影响，这个问题便转化成了一个01背包 ，从而得到了转移方程。

设$f(i,c,h)$为选择第$i$个，已经选择$c$个，在高度为$h$下的面积最大值，则：

时间复杂度为$O(n^3)$，可以通过。

memset(dp,-0x3f,sizeof dp);
for(int i=0;i<=n;i++) dp[i][0][0]=0;
for(int i=1;i<=n;i++)
for(int j=1;j<=k;j++)
for(int h=tot;h>=a[i].y;h--)//注意此处应倒序
dp[i][j][h]=max(dp[i-1][j][h],dp[i-1][j-1][h-a[i].y]+(2*h-a[i].y)*a[i].x);

Step 3. 记忆化

实际上，许多$h$在答案的求解中不会起到任何贡献，计算他们却浪费的大量时间。使用记忆化搜索来进一步优化常数。