JOI 10 本選 Books ( DP )

Books | Aizu Online Judge
ナップサックするだけ。

#include <bits/stdc++.h>
using namespace std;
const int MAXN = 2e3 + 3;
const int MAXK = MAXN;
const int MAXC = 1e5 + 5;
const int MAXG = 10 + 2;

void upmax(int &x, int v){ if( x < v ) x = v; }

int n, k;
int c[ MAXN ], g[ MAXN ];

vector<int> book[ MAXG ];

int dp[ MAXG ][ MAXN ]; // considered until genre / took how much in tot
int val[ MAXG ][ MAXN ]; // value of n books in genre g

void solve(){
    for(int i = 0; i < n; ++i)
        book[ g[ i ] ].push_back( c[ i ] );
    for(int i = 1; i <= 10; ++i){
        sort( book[ i ].begin(), book[ i ].end(), greater<int>() );
        for(int j = 0; j < book[ i ].size(); ++j)
            val[ i ][ j + 1 ] = val[ i ][ j ] + book[ i ][ j ] + 2 * j;
    }
    for(int i = 1; i <= 10; ++i)
        for(int j = 0; j <= k; ++j)
            for(int t = 0; t <= book[ i ].size(); ++t)
                upmax( dp[ i + 1 ][ j + t ], dp[ i ][ j ] + val[ i ][ t ] );
    printf("%d\n", dp[ 11 ][ k ]);
}

int main(){
    scanf("%d%d", &n, &k);
    for(int i = 0; i < n; ++i)
        scanf("%d%d", &c[ i ], &g[ i ]);
    solve();
    return 0;
}