JOI 2011 本選 「古本屋」 AOJ0561 (Books) 解答

DP

頭悪すぎて謎な漸化式になったがなぜか通った。

闇である。

以前にも解いてたっぽい

第10回日本情報オリンピック 本選 「古本屋」 AOJ0561 (Books) - intさわだんのBlack History

#include <bits/stdc++.h>
using namespace std;
 
int n,k,jk[12],ja[12][2003],dp[12][2003],ans;
 
int main(){
    scanf("%d%d",&n,&k);
    for(int i = 0;i < n;i++){
        int c,g;
        scanf("%d%d",&c,&g);
        ja[g][jk[g]++] = c;
    }
 
    for(int i = 1;i <= 10;i++){
        sort(ja[i],ja[i] + jk[i],greater<int>());
    }
    for(int i = 1;i <= 10;i++){
        for(int j = 1;j < jk[i];j++){
            ja[i][j] += ja[i][j-1] + j*2;
        }
    }
 
    for(int i = 1;i <= 10;i++){
        for(int j = 1;j <= k;j++){
            dp[i][j] = max(dp[i][j],dp[i-1][j]);
        }
        for(int j = 1;j <= jk[i];j++){
            for(int l = j;l <= k;l++){
                dp[i][l] = max(dp[i][l],dp[i-1][l-j]+ja[i][j-1]);
                ans = max(ans,dp[i][l]);
            }
        }
    }
 
    printf("%d\n",ans);
    return 0;
}