HDU 2159二次元完全リュック(二次元料金)
2443 ワード
FATE
Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others) Total Submission(s): 10380 Accepted Submission(s): 4926
Problem Description
最近xhdはFATEというゲームをしていて、極品の装備を得るために、xhdは絶えず怪を殺して任務をしています.やがてxhdは殺しに嫌悪感を抱き始めたが、殺しによって最後のレベルを上げざるを得なかった.現在の問題は、xhdが最後のレベルに上昇するにはnの経験値が必要であり、xhdはmの忍耐度を残しており、怪xhdを殺すたびに相応の経験を得て、相応の忍耐度を減らすことである.忍耐度が0以下に下がると、xhdはこのゲームをしません.xhdは彼がせいぜいsだけを殺すと言った.すみません、彼はこの最後のレベルに上がることができますか?
Input
入力データには複数のグループがあり、各グループのデータの最初の行に対してn,m,k,s(0
Output
出力がこのレベルに上昇しても残る最大忍耐度は、このレベルの出力-1を上昇できない場合です.
Sample Input
Sample Output
Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others) Total Submission(s): 10380 Accepted Submission(s): 4926
Problem Description
最近xhdはFATEというゲームをしていて、極品の装備を得るために、xhdは絶えず怪を殺して任務をしています.やがてxhdは殺しに嫌悪感を抱き始めたが、殺しによって最後のレベルを上げざるを得なかった.現在の問題は、xhdが最後のレベルに上昇するにはnの経験値が必要であり、xhdはmの忍耐度を残しており、怪xhdを殺すたびに相応の経験を得て、相応の忍耐度を減らすことである.忍耐度が0以下に下がると、xhdはこのゲームをしません.xhdは彼がせいぜいsだけを殺すと言った.すみません、彼はこの最後のレベルに上がることができますか?
Input
入力データには複数のグループがあり、各グループのデータの最初の行に対してn,m,k,s(0
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
#include<bits/stdc++.h>
using namespace std;
int a[1000], v[1000],dp[1010][1010];
int main()
{
int n,m,k,s;
while(~scanf("%d%d%d%d",&n,&m,&k,&s))
{
for(int i=0;i<k;i++)
{
scanf("%d%d",&a[i],&v[i]);
}
//cout<<'$';
memset(dp,0,sizeof(dp));
for(int i=0;i<k;i++)
{
for(int j=v[i];j<=m;j++) //
{
for(int k=1;k<=s;k++) //
dp[j][k]=max(dp[j][k],dp[j-v[i]][k-1]+a[i]);
}
}
int i=0,j,flag=-1;
for(i=0;i<=m;i++)
{
if(flag!=-1)
break;
for(j=0;j<=s;j++)
{
//cout<<dp[i][j]<<endl;
if(dp[i][j]>=n)
{
flag=i;
break;
}
}
}
if(flag!=-1)
printf("%d
",m-flag);
else
printf("-1
");
}
return 0;
}