FATE-HSU-2159-ダイナミックプランニングカウント法
2040 ワード
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
Sample Output
数えてください.
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(0
出力がこのレベルに上昇しても残る最大忍耐度は、このレベルの出力-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;
}