Aizu Online Judge 0561 - Books

問題

http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0561

日本語なので省略.

解法

動的計画法です.
あるジャンルにおいて, 本を冊選ぶとします. このとき最も高額で売るためには金額が最も高い方から冊選ぶことが最適です. あとはジャンルと選んだ本の冊数でナップザックです.

ソースコード

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

vector<int> ci[10];
vector<int> items[10];
int dp[11][2020];
  
int main() {
    int N, K;
    cin >> N >> K;

    for (int i = 0; i < N; i++) {
        int c, g;
        cin >> c >> g;
        ci[g - 1].push_back(c);
    }

    for (int i = 0; i < 10; i++) {
        sort(ci[i].begin(), ci[i].end(), greater<int>());

        items[i] = vector<int>(ci[i].size());
        for (int j = 0; j < ci[i].size(); j++) {
            int sum = 0;
            for (int k = 0; k <= j; k++) {
                sum += ci[i][k];
            }
            items[i][j] = sum + j * (j + 1);
        }
    }

    for (int i = 0; i < 10; i++) {
        for (int j = 0; j <= K; j++) {
            dp[i + 1][j] = max(dp[i + 1][j], dp[i][j]);
            for (int k = 0; k < items[i].size(); k++) {
                if (j + k + 1 <= K) {
                    dp[i + 1][j + k + 1] = max(dp[i + 1][j + k + 1], dp[i][j] + items[i][k]);
                }
            }
        }
    }
    cout << dp[10][K] << endl;

    return 0;
}

感想

TLE本の練習問題です. DPは解けると楽しいですね.