Posted on 2009-04-24 11:12
superman 阅读(87)
评论(0) 编辑 收藏 引用 所属分类:
USACO
1 #include <iostream>
2
3 using namespace std;
4
5 int main()
6 {
7 freopen("inflate.in", "r", stdin);
8 freopen("inflate.out", "w", stdout);
9
10 int n, m;
11 int w[10000];
12 int v[10000];
13 int f[10001] = { 0 };
14
15 cin >> m >> n;
16 for (int i = 0; i < n; i++)
17 cin >> v[i] >> w[i];
18
19 for (int i = 0; i < n; i++)
20 for (int j = w[i]; j <= m; j++)
21 f[j] >?= (f[j - w[i]] + v[i]);
22
23 cout << f[m] << endl;
24
25 return 0;
26 }
27