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; }