2012 MultiUniversity Training Contest 2

　　原本以为根据DPS排序个序就可以了，经过几次wa后，想起POJ上的一道题类似的题，贪心算法，根据DPS/HP从大到小排序，具体证明写出下面的式子推导一下就可以了。

　　(A.DPS + B.DPS) * A.HP + B.DPS * B.HP > (A.DPS + B.DPS) * B.HP + A.DPS * A.HP <=> A.DPS / A.HP > B.DPS / B.HP

　　官方解题报告说的状态压缩DP。

View Code

 1 #include <stdio.h>
 2 #include <string.h>
 3 #include <algorithm>
 4 #define N 25
 5 
 6 struct enermy
 7 {
 8     int DPS, HP; 
 9 }e[N];
10 
11 bool cmp(enermy a, enermy b)
12 {
13     return (((double)a.DPS) / a.HP) > (((double)b.DPS) / b.HP); // 一定要转为浮点数比较，避免取整带来的错误
14 }
15 
16 int main()
17 {
18     int i, n, sum, res;
19     while(scanf("%d", &n) != EOF)
20     {
21         sum = res = 0;
22         for(i = 0; i < n; i ++)
23         {
24             scanf("%d%d", &e[i].DPS, &e[i].HP);
25             sum += e[i].DPS;
26         }
27         std::sort(e, e + n, cmp);
28         for(i = 0; i < n; i ++)
29         {
30             res += e[i].HP * sum;
31             sum -= e[i].DPS;
32         }
33         printf("%d\n", res);
34     }
35     return 0;
36 }

　　努力更新中……