FATE-HSU-2159-ダイナミックプランニングカウント法


FATE
Time Limit: 2000/1000 MS (Java/Others)Memory Limit: 32768/32768 K (Java/Others) Total Submission(s): 5189Accepted Submission(s): 2343
Problem Description
最近xhdはFATEというゲームをしていて、極品の装備を得るために、xhdは絶えず怪を殺して任務をしています.やがてxhdは殺しに嫌悪感を抱き始めたが、殺しによって最後のレベルを上げざるを得なかった.現在の問題は、xhdが最後のレベルに上昇するにはnの経験値が必要であり、xhdはmの忍耐度を残しており、怪xhdを殺すたびに相応の経験を得て、相応の忍耐度を減らすことである.忍耐度が0以下に下がると、xhdはこのゲームをしません.xhdは彼がせいぜいsだけを殺すと言った.すみません、彼はこの最後のレベルに上がることができますか?
Input
入力データには複数のグループがあり、各グループのデータの最初の行に対してn,m,k,s(0Output
出力がこのレベルに上昇しても残る最大忍耐度は、このレベルの出力-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

数えてください.
#include <iostream>
using namespace std;
int cost[101], val[101], opt[101], n, m, k, s,cnts[101];
int main() {
	while (cin >> n >> m >> k >> s) {
		for (int i = 0; i < k; i++) {
			cin >> val[i] >> cost[i];
		}
		for (int i = 0; i <= m; i++)
		{
			opt[i] = 0;
			cnts[i] = 0;
		}
		for (int i = 0; i < k; i++) {
			for (int j = cost[i]; j <= m; j++) {
				if(opt[j] < opt[j - cost[i]] + val[i] && cnts[j - cost[i]] < s){
					opt[j] = opt[j - cost[i]] + val[i];
					cnts[j] = cnts[j - cost[i]] + 1;
				}
			}
		}
		if (opt[m] < n)
			cout << -1 << endl;
		else {
			for (int i = 0; i <= m; i++) {
				if (opt[i] >= n) {
					cout << m - i << endl;
					break;
				}
			}
		}
	}
	return 0;
}