けんちょんの競プロ精進記録

競プロの精進記録や小ネタを書いていきます

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

JOI JOI本選 JOI難易度6 AtCoder AOJ 前処理 DP シーケンシャルDP 色に関する問題 価格に関する問題

こういうのは DP！

問題概要

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

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

売値の最大値を求めよ。

制約

  • K \le N \le 2000
  • 1 \le G_{i} \le 10

考えたこと

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

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

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

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

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

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

あとはナップサック問題に対する DP と同じように解ける。計算量は、ジャンル種類数を M (\le 10) として、 O(N \log N + MK^{2}) となる。

コード

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