学步园

题意：需要杀死n个英雄，怎么使自己的受到伤害最小。对面每个英雄有攻击力(DPS)和血量（HP)，回合制，你每次可以打一个英雄，打掉一滴血。对方每回合所以存活的英雄都会攻击你，你掉的血量等于攻击你的英雄攻击力之和。

思路：比赛时没做出来，因为没学状态压缩 但发现大家都用贪心给过了 。。。以dps/hp 排序，先干掉hp小的，dps大的
另一种就是官方的状态压缩DP ：用dp[mask]表示杀死mask集合的敌人时，这些敌人造成的最小hp消耗。有转移方程dp[mask]
= min{dp[mask - {i}] + hp_sum[mask] * dps[i], for all i in
mask}

方法1：
#include <stdio.h>
#include <string.h>

int
dp[1<<20],hp[25],dps[25],hp_sum;

int min (int a,int b)
{
    return a
> b ? b : a;
}
int count_sum (int x)  
//计算出每个x状态的hp的和
{
    int t = 1,i
= 1,ans = 0;
    while (t
<= x)
    {
       
if (x&t)
           
ans += hp[i];
       
t = t<<1;
       
i ++;
    }
    return
ans;
}
int main ()
{
    int
n,i;
    while
(~scanf ("%d",&n))
    {
       
for (i = 1;i <= n;i ++)
           
scanf
("%d%d",&dps[i],&hp[i]);
       
memset (dp,0x3f,sizeof(dp));
       
dp[0] = 0;
       
for (i = 1;i <(1<<n);i
++)    
//遍历所有情况
       
{
           
hp_sum = count_sum(i);
           
int t = 1;
           
int k = 1;
           
while (t <= i)
           
{
               
if
(t&i)   
//i中的某一位为t
                   
dp[i] = min (dp[i],dp[i^t]+hp_sum*dps[k]);
               
t  = t <<1;
               
k
++;          
//k 表示第几个人