hdu 2159 FATE （二維DP）

題意：

一種游戲，殺一個怪需要消耗一定的忍耐度才能得到經驗。

現在需要n經驗才能升級，共有m的忍耐度。

其中怪物有K種，要求最多殺S個怪物。

這個道題有點疑問。為什麼按怪物只有一個也能過啊。！！！！！

自己寫的代碼：

wrong了！！！

[csharp] 
#include"stdio.h" 
#include"string.h" 
int dp[101][101]; 
int MAX(int x,int y) 
{ 
    return x>y?x:y; 
} 
int main() 
{ 
    int N,M,K,S,i,j,k,min; 
    int a[101],b[101]; 
    while(scanf("%d%d%d%d",&N,&M,&K,&S)!=-1) 
    { 
        for(i=1;i<=K;i++) 
            scanf("%d%d",&a[i],&b[i]); 
        memset(dp,0,sizeof(dp)); 
        for(i=1;i<=M;i++) 
        { 
            for(j=1;j<=S;j++) 
                for(k=1;k<=K;k++) 
                    if(i-a[k]>=0) 
                        dp[i][j]=MAX(dp[i][j],dp[i-b[k]][j-1]+a[k]); 
        } 
        if(dp[M][S]<N) 
            printf("-1\n"); 
        else 
        { 
            int min; 
            min=M; 
            for(i=1;i<=M;i++) 
            { 
                for(j=1;j<=S;j++) 
                    if(dp[i][j]>=N&&dp[i][j]<min) 
                        min=i; 
            } 
            printf("%d\n",M-min); 
        } 
    } 
    return 0; 
} 

網上找了一個！！
ＡＣ了

[csharp] 
/*d[i][j] : 用i的忍耐度，j的殺怪次數，可以獲得的最大經驗值
狀態轉移：d[i][j] = max{d[i - a[k]][j - 1] + b[k], 1 <= k <= K}
邊界：全部初始化為0
答案：尋找最小的i使得d[i][j] >= N*/ 
 
#include<stdio.h> 
#include<memory.h> 
int a[125], b[125], d[105][105]; 
int main() 
{ 
    //freopen("E:/in.txt", "r", stdin); /// 
    int N, M, K, S, i, j, k; 
    while(scanf("%d%d%d%d", &N, &M, &K, &S) != EOF) 
    { 
        for(i = 1; i <= K; i++) scanf("%d%d", &a[i], &b[i]); 
        memset(d, 0, sizeof(d)); 
        for(i = 1; i <= M; i++) 
        { 
            for(j = 1; j <= S; j++) 
                for(k = 1; k <= K; k++) if(i - b[k] >= 0) 
                { 
                    if(d[i - b[k]][j - 1] + a[k] >= d[i][j]) 
                        d[i][j] = d[i - b[k]][j - 1] + a[k]; 
                } 
                if (d[i][S] >= N) break; 
        } 
         
         
        printf("%d\n", M - i); 
         
         
    } 
     
    return 0; 
}