HDU-2159(2 Dリュックサックテンプレート問題)

3334 ワード

ACM テンプレートの問題 DP

FATE
Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others) Total Submission(s): 13380 Accepted Submission(s): 6327
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

Author

Xhd

Source

2008信息工程学院集训队——选拔赛

Recommend

linle

解题思路:这道题比较水一些，是一个二维费用背包，意味着选一个物品的时候对于费用的使用，存在两种情况的改变，而且同时要满足，这道题在做的时候，要特别分清楚到底谁是背包谁不是，我一开始都弄错了，导致错了几次改了一下

#include    
#include  
#include  
#include    
#include    
#include    
#include   
#include  
#include   
#include    
#include   
#include  
using namespace std;

int a[105], b[105], dp[105][105], n, m, k, s, i, j, u, ans;
int main()
{
	while (cin >> n >> m >> k >> s)
	{
		memset(a, 0, sizeof(a));
		memset(b, 0, sizeof(b));
		memset(dp, 0, sizeof(dp));
		for (i = 1; i <= k; i++)
		{
			cin >> a[i] >> b[i];
		}
		ans = 1000;
		for (i = 1; i <= k; i++)
		{
			for (j = b[i]; j <= m; j++)
			{
				for (u = 1; u <= s; u++)
				{
					dp[j][u] = max(dp[j][u], dp[j - b[i]][u - 1] + a[i]);
					if (dp[j][u] >= n)
					{
						//cout << j << u << endl;
						ans = min(ans, j);
					}
				}
			}
		}
		if (ans > m)
		{
			cout << -1 << endl;
		}
		else
		{
			cout << m - ans << endl;
		}
	}
}

菜鳥プログラミングのjavaチェック漏れ--GridBagLayoutレイアウト

Java webのjsp/servlet