TopCoder SRM 796 : Div1 Easy Div2 Hard ChristmasBatteries

またポカミスやらかした。
https://community.topcoder.com/stat?c=problem_statement&pm=16717&rd=18432

問題

N個のアイテムがあり、それぞれ使用にバッテリーを0～4個消費する。
また、アイテムを入手したときのうれしさが設定されている。

合計バッテリーB個以下で利用できるアイテムの集合のうち、うれしさの総和の最大値を求めよ。

解法

Bが小さいので、DPで解いてもよいしバッテリー1・2・3・4個使うアイテムの個数を総当たりして、それぞれ上位から選んでもよい。

vector<ll> V[5];

class ChristmasBatteries {
	public:
	int mostFun(int B, int N, int X, int Y, int Z, int M) {
		int i;
		FOR(i,5) V[i].clear();
		int sum=0;
		FOR(i,N) {
			int a=(1LL*X*i*i+1LL*Y*i+Z)%M;
			if(i%5==0) sum+=a;
			V[i%5].push_back(a);
		}
		FOR(i,5) sort(ALL(V[i]));
		FOR(i,5) reverse(ALL(V[i]));
		
		int ma=0;
		int a1,a2,a3,a4;
		for(a1=0;a1<=min(B,(int)V[1].size());a1++) {
			for(a2=0;a2<=V[2].size()&&a1+a2*2<=B;a2++) {
				for(a3=0;a3<=V[3].size()&&a3*3+a2*2+a1<=B;a3++) {
					for(a4=0;a4<=V[4].size()&&a4*4+a3*3+a2*2+a1<=B;a4++) {
						int tot=0;
						FOR(i,a1) tot+=V[1][i];
						FOR(i,a2) tot+=V[2][i];
						FOR(i,a3) tot+=V[3][i];
						FOR(i,a4) tot+=V[4][i];
						ma=max(ma,tot);
					}
				}
			}
		}
		
		
		return sum+ma;
	}
}

まとめ

いまいち狙いがわからない問題…。