2017百度之星资格赛：1003. 度度熊与邪恶大魔王

import java.util.*;
public class Main {
    static int n,m;//n只怪兽，m种技能
    static int[] k = new int[1005];//第i种攻击方式消耗的晶石
    static int[] p = new int[1005];//第i种攻击方式的伤害
    static int[] a = new int[100005];//第i只怪兽的生命值
    static int[] b = new int[100005];//第i只怪兽的防御力
    static int[][] dp = new int[1005][11];
    static int INF = 99999999;
    //dp[i][j]的值表示杀掉一个生命值为i，防御力为j的怪物所需的最少晶石
    public static void main(String[] args) {
        Scanner cin = new Scanner(System.in);
        while(cin.hasNext()) {
            int max_a = 0,max_b = 0,max_p = 0;
            n = cin.nextInt();
            m = cin.nextInt();
            for(int i = 1;i <= n;i++) {
                String tmpa = cin.next();
                String tmpb = cin.next();
                a[i] = Integer.parseInt(tmpa);
                b[i] = Integer.parseInt(tmpb);
                max_a = Math.max(a[i],max_a);//记录最大的生命值
                max_b = Math.max(b[i],max_b);//记录最大的防御力
            }
            for(int i = 1;i <= m;i++) {
                String tmpk = cin.next();
                String tmpp = cin.next();
                k[i] = Integer.parseInt(tmpk);
                p[i] = Integer.parseInt(tmpp);
                max_p = Math.max(p[i],max_p);//记录最大的伤害
            }
            if(max_p <= max_b) {
                System.out.println("-1");
                continue;
            }
            for(int i = 0;i <= max_b;i++) {//枚举防御力
                dp[0][i] = 0;//生命值为0的怪物所需的晶石为0
                for(int j = 1;j <= max_a;j++) {//生命值
                    dp[j][i] = INF;
                    for(int l = 1;l <= m;l++) {//枚举所有的技能
                        if(p[l] > i) {
                            if(p[l] - i >= j)//能一招打死
                                dp[j][i] = Math.min(dp[j][i],k[l]);
                            else//一招打不死
                                dp[j][i] = Math.min(dp[j][i],dp[j - (p[l] - i)][i] + k[l]);
                        }
                    }
                }
            }
            long ans = 0;
            for(int i = 1;i <= n;i++) 
                ans += dp[a[i]][b[i]];
            System.out.println(ans);
        }
    }
}