leetcode-go/poj/3624.charm-bracelet/main.cc

#include <cstdio>
#include <cstring>

#define MAX(x, y) ((x) > (y) ? (x) : (y))

using namespace std;

const int N = 3402, M = 12880;

int W[N], D[N], dp[M + 1];

int main() {
  int n, m;
  scanf("%d %d", &n, &m);
  for (int i = 0; i < n; i++) scanf("%d %d", &W[i], &D[i]);
  // dp[i][j] means the max rating under weight j from former i objects.
  // dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - W[i - 1]] + D[i - 1])
  for (int i = 0; i <= m; i++) dp[i] = W[0] <= i ? D[0] : 0;
  for (int i = 2; i <= n; i++)
    for (int j = m; 0 < j; j--)
      if (W[i - 1] <= j) dp[j] = MAX(dp[j], dp[j - W[i - 1]] + D[i - 1]);
  printf("%d\n", dp[m]);
}