AtCoder Beginner Contest 015 D: 高橋くんの苦悩

解法

DP

コード

#include <cstdio>
#include <iostream>
#include <sstream>
#include <fstream>
#include <iomanip>
#include <algorithm>
#include <cmath>
#include <string>
#include <vector>
#include <list>
#include <queue>
#include <stack>
#include <set>
#include <map>
#include <bitset>
#include <numeric>
#include <limits>
#include <climits>
#include <cfloat>
#include <functional>
using namespace std;

int main() {
  int W, N, K;
  cin >> W >> N >> K;
  vector<int> A(N), B(N);
  for (int i = 0; i < N; ++i) cin >> A[i] >> B[i];

  vector<vector<vector<int>>> dp(
      N + 1, vector<vector<int>>(K + 1, vector<int>(W + 1, -1)));
  dp[0][0][0] = 0;
  int ans = 0;
  for (int i = 0; i < N; ++i) {
    for (int k = 0; k < K; ++k) {
      for (int w = 0; w <= W; ++w) {
        if (dp[i][k][w] < 0) continue;
        dp[i + 1][k][w] = max(dp[i + 1][k][w], dp[i][k][w]);
        if (w + A[i] <= W) {
          dp[i + 1][k + 1][w + A[i]] =
              max(dp[i + 1][k + 1][w + A[i]], dp[i][k][w] + B[i]);
          ans = max(ans, dp[i + 1][k + 1][w + A[i]]);
        }
      }
    }
  }
  cout << ans << endl;

  return 0;
}