JOI 古本屋(Books)

Quiz

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

AC code

http://judge.u-aizu.ac.jp/onlinejudge/review.jsp?rid=4146908#1

要素

• ソート
• 累積和
• DP

解法

• 各ジャンルごとに高い順にソートしてよい
• そしてDP

// ジャンル i までで
// 合計 j 冊売るときの最大価格
ll dp[10][2010];

その他

• 非公式難易度は7
  • https://docs.google.com/spreadsheets/d/1zXDtkFmskO5NSxkqck8uDbcJtAhTVZtzPh2hLw64Sw4/edit?pli=1#gid=2075237676
• ジャンル（種類）を添え字としたDP, 新鮮だった
• 公式解説用意してほしい
  • https://www.ioi-jp.org/joi/2010/2011-ho-tasks_data/index.html

Code (抜粋)

// genre iまでで
// 合計j冊売るときの最大価格
ll dp[10][2010];

int main(){
    cin.tie(0);
    ios::sync_with_stdio(false);

    // input
    ll N,K;
    cin >> N >> K;

    VV A(10); // 10種のジャンルごとに本を登録
    rep(i, N){
      ll p,g;cin>>p>>g;
      g--;
      A[g].push_back(p);
    }

    // 各ジャンルで高い値段順にソート
    rep(i, 10){
      RSORT(A[i]);
    }

    AccSum Acc[10];
    rep(i, 10){
      Acc[i] = AccSum(A[i]);
    }

    rep(i, 10){
      dp[i][0] = 0;
    }

    // ジャンル0
    FOR(sell, 1, SZ(A[0])+1){
      ll bonus = sell * (sell-1);
      dp[0][sell] = Acc[0].sum(0, sell-1) + bonus;
    }

    FOR(g, 1, 10){ // genre
      FOR(sum, 1, K+1){ // 累計で売る冊数
        dp[g][sum] = dp[g-1][sum];
        FOR(a, 1, SZ(A[g])+1){ // 今回のジャンルを売る冊数
          ll bonus = a * (a-1);
          ll price_sum = Acc[g].sum(0, a-1); // 本自体の売値
          if(sum-a<0) break;
          chmax(dp[g][sum], dp[g-1][sum-a] + bonus + price_sum);
        }
      }
    }

    ll ans = dp[9][K];
    p(ans);
    
    return 0;
}