题意：
一种游戏，杀一个怪需要消耗一定的忍耐度才能得到经验。
现在需要n经验才能升级，共有m的忍耐度。
其中怪物有K种，要求最多杀S个怪物。
这个道题有点疑问。为什么按怪物只有一个也能过啊。！！！！！
自己写的代码：
wrong了！！！
#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;
}
网上找了一个！！
ＡＣ了
/*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;
}