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

好像是自己第一次独自做出来的DP问题, 也是很感动

// 百度之星2017, 资格赛, 1003
// 2017.8.6  jian

#include <cstdio>
#include <algorithm>
#include <iostream>
#include <cstring>
using namespace std;

typedef long long ll;
const int maxn = 100005;
const int maxm = 1002;
const ll INF = 0x3f3f3f3f3f3f3f3f;
int a[maxn], b[maxn], kk[maxm], p[maxm];
ll dp[maxm][maxm], w[maxm][12];

int main(){
    int n, m;
    // 因为dpmemset后是8个字节的0x3f, 所以上面的INF也是8个字节的0x3f
    memset(dp, 0x3f, sizeof(dp));
    for(int i=0;i<=maxm;i++){
        // 血量为0的时候就打败了, 不用花什么晶石了;
        dp[i][0] = 0;
    }
    while(scanf("%d%d", &n, &m) == 2){
        memset(w, 0, sizeof(w));
        for(int i=0;i<n;i++){
            scanf("%d%d", &a[i], &b[i]);
            // 统计血量为a[i], 防御为b[i]的怪兽的数量
            // 之后就只需要计算一次  打败一只血量为a[i],防御为b[i]的需要多少晶石;
            // 然后在乘以这样的怪兽的数量, 累计求和
            w[a[i]][b[i]]++;
        }
        for(int i=0;i<m;i++){
            scanf("%d%d", &kk[i], &p[i]);
        }
        ll ans = 0;
        bool flag = false;
        for(int i=0;i<11;i++){
            for(int j=0;j<m;j++){
                for(int k=0;k<maxm;k++){
                    // 如果攻击小于等于防御的话是不能打败的;
                    if(p[j] - i <= 0){
                        dp[j+1][k] = dp[j][k];
                    }
                    // 如果血量少于要扣的血, 那么血量减到0就行了;
                    else if(k < p[j] - i){
                        dp[j+1][k]=min(dp[j][k],dp[j+1][0]+kk[j]);
                    }
                    // 然后下面好像就是正常的完全背包了;
                    // 不过是取得最小值, 所以前面的dp数组memset的也是INF;
                    else{
                        dp[j+1][k]=min(dp[j][k],dp[j+1][k-(p[j]-i)]+kk[j]);
                    }
                }
            }
            for(int j=0;j<maxm;j++){
                // 如果dp数组没有更新还是INF的话, 那么说明怪兽不能被打败;
                // 不过w[j][i]==0的话,都没有这种怪兽了, dp数组更不更不影响了;
                if(w[j][i] != 0 && dp[m][j] == INF){
                    ans = -1;
                    flag = true;
                    break;
                }
                // 其实讲道理的话dp数组里的每个值都是不会超过1e9的, 
                // 4个字节的0x3f也是够用的, 但是乘了w数组就不会爆啊;
                // 为了保险我就全开long long 了;=-=
                ans += w[j][i] * dp[m][j];
            }
            // 只要有一只怪兽不能被打败就是 -1 了;
            if(flag) break;
        }
        printf("%lld\n", ans);
    }
    return 0;
}