uva 10819 - Trouble of 13-Dots

 1 /*
 2  Problem link
 3  Type: DP, knapsack(0/1)
 4  */
 5  #include <iostream>
 6  #include <cstdio>
 7  #include <cstring>
 8  #include <cmath>
 9  using namespace std;
10  
11  const int maxn = 110;
12  const int maxm = 11000;
13  const int oo = 2000000;
14  
15  int n,s;
16  int v[maxn], w[maxn];
17  int f[maxm][maxn];
18  
19  int solve();
20  
21  int main()
22  {
23      while (!cin.eof())
24      {
25          cin >> s >> n;
26          s+= 200;
27          if (cin.eof()) break;
28          for (int i=1; i<=n; i++) cin >> w[i] >> v[i];
29          cout << solve() << endl;
30      }
31      return 0;
32  }
33  
34  int solve() {
35      int result = 0, total = 0;
36      for (int i=0; i<=n; i++)
37      {
38          total += w[i];
39          for (int j=0; j<=s; j++) f[j][i] = -oo;
40      }
41      f[0][0] = 0;
42      for (int j=1; j<=n; j++)
43          for (int i=0; i<=min(total,s); i++)
44              if (w[j]<=i) f[i][j] = max(f[i-w[j]][j-1]+v[j],f[i][j-1]);
45              else f[i][j] = f[i][j-1];
46      s-=200;
47      for (int i=0; i<=s; i++) result = max(result,f[i][n]);
48      for (int i=2001; i<=s+200; i++) result = max(result,f[i][n]);
49      return(result);
50  }