百度の星1003度の熊と邪悪な大魔王

度度度熊と悪の大魔王
Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)
Problem Description度熊は可爱い姫を救うため、邪悪な大魔王と戦う.邪悪な大魔王の下にはn体のモンスターがおり、それぞれのモンスターにはa[i]の生命値とb[i]の防御力がある.度度熊は全部でm種類の攻撃方式を持ち、i種類目の攻撃方式はk[i]の結晶石を消費し、p[i]点ダメージを与える.もちろん、度度熊がi番目のスキルを使ってj番目のモンスターに打ち込むと、j番目のモンスターの生命値がp[i]-b[j]減少し、もちろんダメージが防御より小さくなると攻撃は奏効しません.モンスターの生命値が0以下になると、モンスターは消滅します.もちろん各スキルは無限回使用できます.度の熊は少なくともどれだけの晶石を携帯して、すべての怪獣Inputの本題を消滅していくつかの組のテストデータを含みます.1行目の2つの整数n,mは、n個のモンスター、m種のスキルを表す.次のn行は、行ごとに2つの整数、a[i],b[i]で、それぞれモンスターの生命値と防御力を表します.さらにm行、1行あたり2つの整数k[i]とp[i]は、それぞれスキルの消費結晶石数とスキルのダメージ値を表す.データ範囲:1<=n<=1000001<=m<=1000 1<=a[i]<=1000<=b[i]<=10 0<=k[i]<=1000000<=p[i]<=1000 Output各テストデータに対して最小の結晶石消費量を出力し、全てのモンスターを負かすことができない場合、出力-1 Sample Input 1 2 3 3 3 5 10 6 8 8 8 Sample Output 6 18
最も重要なアルゴリズム部分はdpです

for(int td=0; td<=maxd; td++) {
    for(int i=1; i<=maxHP; i++) {
        long long t = 0;
        bool flag=true;
        for(int j=0; jif(ski[j].att<=0)continue;
            if(i-ski[j].att<=0) {
                if(t>ski[j].spend||flag) {
                    t=ski[j].spend;
                    flag = false;
                }
            } else if(flag||t>spe[i-ski[j].att][td]+ski[j].spend) {
                t=spe[i-ski[j].att][td]+ski[j].spend;
                flag = false;
            }
        }
        spe[i][td]=t;
    }
    for(int i=0; i

試合後更新
タイトルの意味によって完全バックパックで解决し、タイトルから与えられたデータの大きさを见て、计算时に生命値が1-1000、防御値が0-10のすべての场合を计算し、それに対応するすべての场合のモンスターを加えて、消费した水晶数を得ることができます.

#include
#define MAX 1050

using namespace std;
int n,m;
long long int spe[MAX][11];//
long long int num[MAX][11];//           num[100][2]     100     2      
long long int ans;
struct skill {
    int att,spend;
} ski[MAX];

int main() {
    while(cin>>n>>m) {
        ans=0;
        memset(num,0,sizeof(num));
        memset(spe,0,sizeof(spe));
        int maxa=0,maxd=0,maxHP=0,a,b,k,p;
        for(int i=0; icin>>a>>b;
            num[a][b]++;
            maxHP = max(maxHP,a);
            maxd = max(maxd,b);//             
        }
        for(int i=0; icin>>k>>p;
            ski[i].spend=k;
            ski[i].att=p;
            maxa = max(maxa,ski[i].att);//          
        }
        if(maxa<=maxd) {//                        ，       
            cout<1<continue;
        }
        for(int td=0; td<=maxd; td++) {
            for(int i=1; i<=maxHP; i++) {//                   、           
                long long t = 0;
                bool flag=true;
                for(int j=0; j//    
                    if(ski[j].att<=0)continue;
                    if(i-ski[j].att<=0) {
                        if(t>ski[j].spend||flag) {
                            t=ski[j].spend;
                            flag = false;
                        }
                    }else if(flag||t>spe[i-ski[j].att][td]+ski[j].spend) {
                        t=spe[i-ski[j].att][td]+ski[j].spend;
                        flag = false;
                    }
                }
                spe[i][td]=t;
            }
            for(int i=0;i//             ，      1                   
        }
        for(int i=0; i<=maxHP; i++) {
            for(int j=0; j<=10; j++) {
                ans+=(spe[i][j]*num[i][j]);//        
            }
        }
        cout<return 0;
}