第10回日本情報オリンピック 本選 「古本屋」 AOJ0561 (Books)

DP

dp[i][j]:=ジャンルiまでの本をj冊売るときの買い取り価格の最大値.

各ジャンルについてソートしてi冊売ったときの値段を記録しておきます。

#include <bits/stdc++.h>

using namespace std;

int n,dp[2003][2003],b[11][2003],k,co[11];
int main(){
	scanf("%d%d",&n,&k);
	for(int i = 1;i <= 10;i++)co[i]=1,b[i][0] = 100000000;
	for(int i = 0;i < n;i++){
		int a1,a2;
		scanf("%d%d",&a1,&a2);
		b[a2][co[a2]] = a1;
		co[a2]++;
	}
	for(int i = 1;i <= 10;i++)sort(b[i],b[i] + co[i],greater<int>());
	for(int i = 1;i <= 10;i++){ 
		b[i][0] = 0;
		for(int j = 1;j < co[i];j++){
			b[i][j] += b[i][j-1] + (j-1)*2;
		}
	}
	for(int i = 1;i <= 10;i++){
		for(int j = 1;j <= k;j++){
			for(int l = 0;l <= min(co[i]-1,j);l++){
				dp[i][j] = max(dp[i][j],dp[i-1][j-l]+b[i][l]);
			}
		}
	}
	printf("%d\n",dp[10][k]);
	return 0;
}