JOI 2010 本選 B 古本屋

問題

見た感じ

まず、セールがあるとはいえ、価格の高いやつから売っていくのが最適やろということで、各カテゴリーの中で降順にソートして、そこからナップザックすればよさそう。
計算するのは、以下の漸化式

dp[i][j]=i番目までのカテゴリーからj個うった時の儲けの最大値\\
g[i]::カテゴリーiに含まれる本の集合、ソート済み\\
dp[i+1][j]=\max_{l<=min(j,|g[i+1]|)}dp[i][j-l]+\sum_{m=0}^{l-1}g[i][m] + l*(l-1)

解法

ソートして、ナップザックしていく。
roopの中で想定していない計算(例えば、全部で7個選ぶときで先に3個決まってるけど$|g[i]|<4$で空白ができる)とかも慎重に実装しないと出てくるけど今回はmaxをとるから大丈夫

ソースコード

const int N_MAX=2001;
int n,k,c[N_MAX],dp[11][N_MAX];
vint g[10];

int solve(){
    rep(i,10){
        sort(g[i].begin(),g[i].end(),[](int i,int j)->bool{return c[i]>c[j];});
    }
    int count=0,m;
    rep1(i,10){
        m=g[i-1].size();
        count+=m;
        rep(j,min(k,count)+1){
            if(j==0){
                dp[i][0]=0;
                continue;
            }
            int res=dp[i-1][j],gsum=0;
            for(int l = 1;l<=min(j,m);l++){
                gsum+=c[g[i-1][l-1]];
                res=max(res,dp[i-1][j-l]+gsum+l*(l-1));
            }
            dp[i][j]=res;
        }
    }
    return dp[10][k];
}

int main(){
    int i,x;
    //入力
    cin>>n>>k;
    rep(i,n){
        cin>>c[i]>>x;
        g[x-1].push_back(i);
    }
    //処理
    int ans=solve();
    //出力
    cout << ans <<endl;
}
```　　

##気づいたこと
セール代のとこが別にほかの個数の関数でも同じ解法でいけるね