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

1003题目[度度熊与邪恶大魔王]

题目描述

给定n个怪兽的血量和防御值，以及m个技能的伤害和花费。求打败n个怪兽需要的花费最小值

题目思路

• 完全背包

  从题目中所说，每个技能可以使用无限次得知可以通过完全背包来解决。

• 复杂度估计

  如果对n个怪兽，每个计算m个技能消灭怪兽的最小花费计算，那么需要 a*b*m*a = 1000 * 10 * 1000 * 1000（即n个怪兽的血量和防御共有1000*10种，每次计算最小花费需要完全背包的时间复杂度1000*1000）这种做法必然超时

• 考虑防御的范围为10

  因此，考虑对于每一个怪兽的血量虽然可能不同，但是相同防御的情况下，对于f[v]来说解都是一样的。所以只需要考虑当前防御值是否计算过，如果计算过，那么直接可以在f[v]中得到答案

  复杂度 b*m*a = 10 * 1000 * 1000

代码

在没有完全理解解法前，建议不要先看代码

#include<iostream>
#include<stdio.h>
#include<memory.h>
using namespace std;

int main(){
    int a[], b[];
    int k[],p[];
    int vdp[][];
    bool flag;
    int N, M;
    __int64 ans;
    //long long ans;
    int INF = ; 
    while(scanf("%d%d", &N,&M)!=EOF){
        ans = ;
        for(int i=;i<N;i++){
            scanf("%d%d",&a[i],&b[i]);
        }
        for(int i=;i<M;i++){
            scanf("%d%d",&k[i],&p[i]);
        }
        for(int i=;i<;i++){
            for(int k=;k<=;k++){
                vdp[k][i] = INF;
            }
            vdp[][i] = ;
        }
        for(int i=;i<;i++){
            for(int j=;j<M;j++){
                if(p[j]-i>){
                    for(int v=p[j]-i; v<=;v++){
                        vdp[v][i] = min(vdp[v][i], vdp[v-(p[j] - i)][i]+k[j]);
                    }
                }
            }
        }
        for(int i=;i<N;i++){
            flag = false;
            int max = INF;
            for(int v=a[i];v<=a[i]+;v++){
                //cout<<v<<" "<<vdp[v]<<endl;
                if(vdp[v][b[i]]!=INF){
                    if(max>vdp[v][b[i]]){
                        max = vdp[v][b[i]];
                    }
                }
            }
            if(max != INF){
                ans += max;
                flag = true;
            }
            if(!flag)
                break;
        }
        if(!flag)
            printf("-1\n");
            //cout<<-1<<endl;
        else{
            printf("%I64d\n",ans);
            //cout<<ans<<endl;
        }
    }
}