最近xhd正在玩一款叫做FATE的游戏，为了得到极品装备，xhd在不停的杀怪做任务。久而久之xhd开始对杀怪产生的厌恶感，但又不得不通过杀怪来升完这最后一级。现在的问题是，xhd升掉最后一级还需n的经验值，xhd还留有m的忍耐度，每杀一个怪xhd会得到相应的经验，并减掉相应的忍耐度。当忍耐度降到0或者0以下时，xhd就不会玩这游戏。xhd还说了他最多只杀s只怪。请问他能升掉这最后一级吗？

10 10 1 10

1 1

10 10 1 9

1 1

9 10 2 10

1 1

2 2

0

-1

1

 1 for(int i=0; i<k; ++i)

 2         {

 3             for(int j=b[i]; j<=m; ++j)

 4             {

 5                 for(int x=1; x<=s; ++x)

 6                 {

 7                     /*

 8                     比如枚举到第一个怪a[i]=5,b[i]=5,那么dp[5-m][1]=5;

 9                     这个时候dp[5-m][2]也被赋值为5了

10                     */

11                     if(dp[j][x]<dp[j-b[i]][x-1]+a[i])

12                     {

13                         dp[j][x]=dp[j-b[i]][x-1]+a[i];

14                     }

15                 }

16             }

17         }

 1 #include<stdio.h>

 2 #include<string.h>

 3 #include<iostream>

 4 #include<algorithm>

 5 #include<math.h>

 6 #include<vector>

 7 #include<queue>

 8 #include<stack>

 9 #include<map>

10 using namespace std;

11 typedef long long ll;

12 const int maxn=110;

13 const int INF=0x3f3f3f3f;

14 const double eps=1e-10;

15 const int mod = 1e9+7;

16 #define mt(A,B) memset(A,B,sizeof(A))

17 #define lson l,m,rt*2

18 #define rson m+1,r,rt*2+1

19 int a[maxn],b[maxn],dp[maxn][maxn];

20 int main()

21 {

22     int n,m,k,s;

23     while(~scanf("%d%d%d%d",&n,&m,&k,&s))

24     {

25         for(int i=0; i<k; ++i)

26         {

27             scanf("%d%d",&a[i],&b[i]);

28         }

29         memset(dp,0,sizeof(dp));

30         for(int i=0; i<k; ++i)

31         {

32             for(int j=b[i]; j<=m; ++j)

33             {

34                 for(int x=1; x<=s; ++x)

35                 {

36                     /*

37                     比如枚举到第一个怪a[i]=5,b[i]=5,那么dp[5-m][1]=5;

38                     dp[5-m][2]也被赋值为5了

39                     */

40                     if(dp[j][x]<dp[j-b[i]][x-1]+a[i])

41                     {

42                         dp[j][x]=dp[j-b[i]][x-1]+a[i];

43                     }

44                 }

45             }

46         }

47         if(dp[m][s]>=n)

48         {

49             for(int i=0; i<=m; ++i)

50             {

51                 if(dp[i][s]>=n)

52                 {

53                     printf("%d\n",m-i);

54                     break;

55                 }

56             }

57         }

58         else

59             printf("-1\n");

60     }

61

62     return 0;

63 }