#include #include int sum,res,i,n; struct node { int hp,dsp; void input() { scanf("%d%d",&dsp,&hp); sum += dsp; } }hero[22]; ///按单位血量的攻击力排序 bool cmp(node a,node b) { return a.dsp*1.0/a.hp > b.dsp*1.0/b.hp; } int main() { while(scanf("%d",&n) == 1) { sum = 0; res = 0; for(i = 0; i < n; ++i) hero[i].input(); std::sort(hero,hero + n,cmp); for(i = 0; i < n; ++i) { res += sum * hero[i].hp; sum -= hero[i].dsp; } printf("%d ",res); } return 0; } 解题报告 1001 Hero 中等偏易题，状态压缩dp，用dp[mask]表示杀死mask集合的敌人时，这些敌人造成的最小hp消耗。有转移方程dp[mask] = min{dp[mask - {i}] + hp_sum[mask] * dps[i], for all i in mask}