POJ1015

题意

现有两方, 给出n个人,每方分别给n个人两个分数分别为a[i],b[i],现要选出m个人,使得m个人两方的和的差的绝对值最小,如果多组解,输出双方和最大的解( 1<=n<=200, 1<=m<=20, 0 <= a[i],b[i]<= 20)

分析

贪心显然不可解

错的思路:dp[i]表示n个人选出i个人的的最佳方案(即绝对值最小),但显然转移出现问题,dp[i+1]可能不是由dp[i]转移过来的(假如:dp[i] 为1, 但也存在-5, 这时若有有个啊a[i]-b[i]==5,显然-5转移过里最佳)

正解

定义:dp[i][k]:n个人中选了i个人绝对值为k的最佳方案(和最大)

转移:显然dp[i][k](-20*m<=k<=20*k)是由dp[i-1][k+x]转移过来,枚举一下转移就好,不存在的状态用-1表示即可,注意枚举顺序

边界:dp[0][0]=0,

要么优秀要么生锈
原文地址:https://www.cnblogs.com/Superwalker/p/7912190.html