记录编号	166551	评测结果	AAAAAAAAAA
题目名称	多人背包	最终得分	100
用户昵称	啊吧啦吧啦吧	是否通过	通过
代码语言	C++	运行时间	0.503 s
提交时间	2015-06-15 16:20:27	内存使用	1.16 MiB

#include<fstream>
#include<climits>
#include<algorithm>

using namespace std;

const int MAXN = 201, MAXV = 5001, MAXK = 51;
int n, k, dp[MAXV][MAXK], wv[MAXN], ww[MAXN], v, sum = 0;
ifstream fi("bags.in");
ofstream fo("bags.out");
#define cin fi
#define cout fo

main()
{
//	ios::sync_with_stdio(0);
	cin >> k >> v >> n;
	for(int i = 1; i <= n; i ++)
		cin >> wv[i] >> ww[i];
		
	for(int i = 0; i <= n; i ++)
		fill(dp[i], dp[i] + k + 1, INT_MIN);
	dp[0][1] = 0;
	for(int i = 1; i <= n; i ++)
		for(int j = v; j >= wv[i]; j --)
		{
			int t1 = 1, t2 = 1, tot = 0, tmp[MAXK];
			while(tot != k)
			{
		        if(dp[j - wv[i]][t1] + ww[i] > dp[j][t2])
		          tmp[++ tot] = dp[j - wv[i]][t1 ++] + ww[i];
		        else
		          tmp[++ tot] = dp[j][t2 ++];
			}
			for(int l = 1; l <= k; l ++)
				dp[j][l] = tmp[l];
		}
	for(int i = 1; i <= k; i ++)
		sum += dp[v][i];
	
	cout << sum;
}