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; 
}