AOJ 0561: Books

ジャンル毎にx冊売った時の合計金額を前計算しておく。
普通にナップサック問題を解けば、解けます。実際には可能かもしれませんが、1次元配列ではDPできませんでした。

#include <algorithm>
#include <cstdio>
#include <vector>
#include <functional>
using namespace std;

vector<int> books[10];
vector<int> sell[10];
int dp[11][2001];

int main(){
	int n,k;
	scanf("%d%d",&n,&k);
	
	for(int i = 0; i < n; i++){
		int a,b;
		scanf("%d%d",&b,&a);
		books[a-1].push_back(b);
	}
	
	for(int i = 0; i < 10; i++) sort(books[i].begin(),books[i].end(),greater<int>());
	
	for(int i = 0; i < 10; i++){
		sell[i].push_back(0);
		for(int j = 0,j_n = min(k,(int)books[i].size()); j < j_n; j++){
			sell[i].push_back(books[i][j]+sell[i][j]+2*j);
		}
	}
	
	for(int i = 0; i < 10; i++){
		for(int j = 0,j_n = sell[i].size(); j <= k; j++){
			for(int l = 0; l<=k; l++){
				dp[i+1][l] = max(max(dp[i+1][l],dp[i][l]),l>=j&&j<j_n?dp[i][l-j]+sell[i][j]:0);
			}
		}
	}
	
	printf("%d\n",dp[10][k]);
	
	return 0;
}