JOI 本選 2011 B - 古本屋 (AOJ 0561, 難易度 6)

こういうのは DP！

• ジャッジページ
• AOJ の問題文

問題概要

冊の古本があって、 番目の本のベース価格は 円である。またこれらの本は 10 種類のジャンルに分かれており、 番目の本のジャンルは で与えられる。

これらの本から 冊を古本屋で売りたい。ただし同じ種類の本を複数冊購入した場合には、より高く売ることができる。具体的には、同じ種類の本が 冊あった場合には、それらの本のベース価格が 円ずつ上昇する。

売値の最大値を求めよ。

制約

• 
• 

考えたこと

とても典型的な DP だけど、とっかかりが難しいかもしれない。こういうときは、何かを固定してみることで突破口が開けることが多い気がする。

今回は、各種類の本を何冊ずつ売るのかを固定してみよう。つまり、種類 の本を 冊ずつ売ることにする。この場合は、各種類 ごとに高い順に 冊売るのが最適だということがわかる。

これがわかればもとの問題の解法も見えてくる。あらかじめ次のデータを求めておく。

• val[i][j] ← 種類 の本を 冊売るとしたときの売値の最大値

そして次のような DP をしよう。

• dp[i][j] ← 10 種類のうち最初の 種類のみを考える。その時点で 冊まで売るとしたときの売値の最大値

あとはナップサック問題に対する DP と同じように解ける。計算量は、ジャンル種類数を として、 となる。

コード

#include <bits/stdc++.h>
using namespace std;

int main() {
    int N, K;
    cin >> N >> K;
    vector<vector<long long>> P(10);
    for (int i = 0; i < N; ++i) {
        long long price, type;
        cin >> price >> type;
        --type;
        P[type].push_back(price);
    }

    // 前処理
    for (int i = 0; i < 10; ++i) sort(P[i].begin(), P[i].end(), greater<long long>());
    vector<vector<long long>> val(10);
    for (int i = 0; i < 10; ++i) {
        val[i].assign(P[i].size()+1, 0);
        for (int j = 0; j < P[i].size(); ++j) {
            val[i][j+1] = val[i][j] + P[i][j];
        }
        for (int j = 0; j < val[i].size(); ++j) {
            val[i][j] += j * (j-1);
        }
    }

    // DP
    vector<vector<long long>> dp(11, vector<long long>(K+1, 0));
    for (int i = 0; i < 10; ++i) {
        for (int j = 0; j <= K; ++j) {
            for (int k = 0; k < val[i].size() && j+k <= K; ++k) {
                dp[i+1][j+k] = max(dp[i+1][j+k], dp[i][j] + val[i][k]);
            }
        }
    }
    cout << dp[10][K] << endl;
}