ZOJ3956 ZJU2017校赛(dp)

题意:给出n对(h,c)  

   记  sumh为选出的h的总和  sumc为选出的c的总和

   你可以从中选出任意多对(可以不选)

   使得  sumh^2-sumh*sumc-sumc^2 最大

   输出最大值

   输入第一行表示数据组数 T

   接下来一行为n,(1 <= n <= 500)

   接下来n行为n对(hi,ci),1 ≤ hi ≤ 10000, 1 ≤ ci≤ 100

   保证所有n的总和不超过5000.

分析:H^2-H*C-C^2

   从这个式子可以看出,当C固定不动的时候

    1)若H>=C,则H越大越好

    2)若H<C,则H越小越好

   注意H小于C的时候,这个式子和为负数,根据题意,我们可以有ans=0,所以这种H<C的情况肯定不是最优,不需要考虑

   综上,我们只关心对于固定的C,求最大的H

   就直接背包了,dp[i][j]表示前i个物品,当ΣC=j的时候,ΣH的最大值

   注意滚动数组滚动下

   最后扫一遍答案

原文地址:https://www.cnblogs.com/wmrv587/p/6711123.html