度度熊与邪恶大魔王
time limit per test 1 second memory limit per test 256 megabytes
Problem Description
度度熊为了拯救可爱的公主，于是与邪恶大魔王战斗起来。 邪恶大魔王的麾下有n个怪兽，每个怪兽有a[i]的生命值，以及b[i]的防御力。 度度熊一共拥有m种攻击方式，第i种攻击方式，需要消耗k[i]的晶石，造成p[i]点伤害。 当然，如果度度熊使用第i个技能打在第j个怪兽上面的话，会使得第j个怪兽的生命值减少p[i]-b[j]，当然如果伤害小于防御，那么攻击就不会奏效。 如果怪兽的生命值降为0或以下，那么怪兽就会被消灭。 当然每个技能都可以使用无限次。 请问度度熊最少携带多少晶石，就可以消灭所有的怪兽。

传送门：HDU6082

Input

本题包含若干组测试数据。 第一行两个整数n，m,表示有n个怪兽，m种技能。 接下来n行，每行两个整数，a[i],b[i]，分别表示怪兽的生命值和防御力。 再接下来m行，每行两个整数k[i]和p[i]，分别表示技能的消耗晶石数目和技能的伤害值。
数据范围: 1<=n<=100000 1<=m<=1000 1<=a[i]<=1000 0<=b[i]<=10 0<=k[i]<=100000 0<=p[i]<=1000

Output

对于每组测试数据，输出最小的晶石消耗数量，如果不能击败所有的怪兽，输出-1

Sample Input

1
2
3
4
5
6
7
8
1 2
3 5
7 10
6 8
1 2
3 5
10 7
8 6

Sample Output

1
2
6
18

题解

看到防御值只有0-10可以将怪兽分类 分别统计个数 dp[i][j] 代表防御值为i 造成伤害为j时的最小消耗 对每一个i做一次完全背包就能知道j从0-2000的dp值(注意为什么是2000) 因为伤害可以溢出 所以dp[i][j]的最小值其实是dp[i][j]到dp[i][2000]的最小值 (溢出最大为999+1000) 最后两重循环将对应的dp值乘以个数就好了复杂度O(1e7)左右
## AC code:(不包含输入类) 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
import java.io.*;  
import java.util.*;  
public class Main {  
    static long maxn=(long) (1e17+6);  
    public static void main(String[] args) {  
        FastScanner sc = new FastScanner();  
        PrintWriter pw = new PrintWriter(System.out);  
        while (sc.hasNext()) {  
            int n=sc.nextInt();  
            int m=sc.nextInt();  
            int[]k=new int[m];  
            int[]p=new int[m];  
            long[][]sum=new long[12][2005];  
            for(int i=0;i<n;i++){  
                int a=sc.nextInt();  
                int b=sc.nextInt();  
                sum[b][a]+=1;  
            }  
            for(int i=0;i<m;i++){  
                k[i]=sc.nextInt();  
                p[i]=sc.nextInt();  
            }  
            long[][]dp=new long[11][2005];  
            for(int i=0;i<11;i++){  
                Arrays.fill(dp[i], maxn);  
            }  
            for(int i=0;i<11;i++){  
                dp[i][0]=0;  
                for(int z=0;z<m;z++){  
                    int t=p[z]-i;  
                    if(t<=0)continue;  
                    for(int j=t;j<=2000;j++){  
                            dp[i][j]=Math.min(dp[i][j], dp[i][j-t]+k[z]);  
                    }  
                }  
                for(int j=2000;j>=0;j--)dp[i][j]=Math.min(dp[i][j], dp[i][j+1]); //非常重要  
            }  
            long res=0;  
            for(int i=0;i<11;i++){  
                for(int j=0;j<=2000;j++){  
                    if(sum[i][j]!=0){  
                        res+=sum[i][j]*dp[i][j];  
                    }  
                }  
            }  
            if(res<maxn)  
                pw.println(res);  
            else  
                pw.println(-1);  
            pw.flush();  
        }  
    }  
}