FATE
Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 7307 Accepted Submission(s): 3371
Problem Description 最近xhd正在玩一款叫做FATE的游戏，为了得到极品装备，xhd在不停的杀怪做任务。久而久之xhd开始对杀怪产生的厌恶感，但又不得不通过杀怪来升完这最后一级。现在的问题是，xhd升掉最后一级还需n的经验值，xhd还留有m的忍耐度，每杀一个怪xhd会得到相应的经验，并减掉相应的忍耐度。当忍耐度降到0或者0以下时，xhd就不会玩这游戏。xhd还说了他最多只杀s只怪。请问他能升掉这最后一级吗？
Input 输入数据有多组，对于每组数据第一行输入n，m，k，s(0 < n,m,k,s < 100)四个正整数。分别表示还需的经验值，保留的忍耐度，怪的种数和最多的杀怪数。接下来输入k行数据。每行数据输入两个正整数a，b(0 < a,b < 20)；分别表示杀掉一只这种怪xhd会得到的经验值和会减掉的忍耐度。(每种怪都有无数个)
Output 输出升完这级还能保留的最大忍耐度，如果无法升完这级输出-1。
Sample Input
10 10 1 10
1 1
10 10 1 9
1 1
9 10 2 10
1 1
2 2
Sample Output
0
-1
1
Author Xhd
Source 2008信息工程学院集训队――选拔赛
Recommend linle | We have carefully selected several similar problems for you: 1171 2955 2844 2191 1114
没有安全A过，在数组卡了，又在二维背包卡了。。。。
i:怪物的种类。t:当前杀怪数。j:已用的耐久度。
#include
#include
using namespace std
; #define M 200
int a
[M
],b
[M
],dp
[M
][M
]; int max
(int x
,int y
) { return x
>y
?x
:y
; } int main(int i
,int j
,int k
) { int n
,t
,m
,g
,V
,s
; while(scanf
("%d%d%d%d"
,&n
,&m
,&k
,&s
)!=EOF
) { memset
(dp
,0
,sizeof(dp
)); for(i
=0
;i
<k
;i
++) { scanf
("%d%d"
,&a
[i
],&b
[i
]); } for(i
=0
;i
<k
;i
++) for(t
=1
;t
<=s
;t
++) for(j
=b
[i
];j
<=m
;j
++) { dp
[t
][j
]=max
(dp
[t
][j
],dp
[t
-1
][j
-b
[i
]]+a
[i
]); //在这里卡得死，t-1写成了t,以为是一维的背包去了。 } for(i
=0
;i
<=m
;i
++) { if(n
<=dp
[s
][i
]) //这样找到的一定就是消耗耐久度最少的，i:0->m.用的越少，剩余越多。 break; } if(i
==m
+1
) //没有一个达到经验数。 printf
("-1\n"
); else printf
("%d\n"
,m
-i
); } return 0
; }