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

补充：软件开发 , C++ ,