2017百度之星资格赛1003度度熊与邪恶大魔王背包DP

#include 
#include 
using namespace std;

const int MAX = 100005;
const int INF = 0x3f3f3f3f;

int n, m;
int dp[1005][12];    //打血量为 i，防御为 j 的怪所需的最少晶石
int a[MAX], b[MAX];
int k[1005], p[1005];
int getK[1005];        //造成 i 伤害需要的晶石数量 

int main(){
//    freopen("input.txt", "r", stdin);
//    freopen("output.txt", "w", stdout);
    
    while(scanf("%d%d", &n, &m) == 2){
        int maxA = 0, maxB = 0;            //最多多少血量和防御 
        for(int i=1; i<=n; i++){
            scanf("%d%d", a+i, b+i);
            maxA = max(maxA, a[i]);
            maxB = max(maxB, b[i]);
        }
        memset(getK, 0x3f, sizeof(getK));
        for(int i=1; i<=m; i++){
            scanf("%d%d", k+i, p+i);
            if(getK[p[i]] <= k[i] || p[i] == 0){    //有更实惠的技能 
                m--; i--; continue;
            }
            getK[p[i]] = k[i];
        }
        
        memset(dp, 0x3f, sizeof(dp));
        for(int i=0; i<=10; i++){
            dp[0][i] = 0;        //怪物血量为 0 时，需要的晶石数量为 0 
        }
        for(int i=1; i<=maxA; i++){        //血量 
            for(int j=0; j<=maxB; j++){    //防御 
                for(int l=1; l<=m; l++){    //晶石 
                    int t = p[l] - j;        //能造成的伤害
                    if(t <= 0){                //如果不能造成伤害
                        continue; 
                    }
                    if(i >= t){            //如果一次打不死 
                        dp[i][j] = min(dp[i][j], dp[i-t][j] + k[l]);
                    }else{
                        dp[i][j] = min(dp[i][j], k[l]);
                    }
                }
            }
        }
        
        long long ans = 0;
        for(int i=1; i<=n; i++){
            if(dp[a[i]][b[i]] < INF){
                ans += dp[a[i]][b[i]];
            }else{
                ans = -1;
                break;
            }
        }
        
        cout < endl;
    }
    
    return 0; 
}