Typical DP Contest : H - ナップザック

ここからは本番に解ききれず解説や他人のソースを参考に回答。
http://tdpc.contest.atcoder.jp/tasks/tdpc_knapsack

問題

N個の物の重さ・価値・色はw[i]、v[i]、c[i]である。
重さW以内・色数C以内で合計価値を最大化せよ。

解法

２つの上限があるナップサック問題。

本番では、まず各色ごとにDPして重さごとの価値を求め、最後に色毎の結果をDPしようとした。
しかしこの処理はO(C^2 W^2)かかりTLE。

Nが小さい点を考慮し、先に色毎の荷物を全部DPしてしまうのではなくて、A色のDPの結果に対しある色の各荷物をDPしていって(A+1)色の結果を求めればよい。
こちらはO(C^2 NW)なので間に合う。

int N,TW,TC;
int W[10001],V[10001],C[10001];
int dpdp[52][10002];
int tmp[10002];
vector<int> WW[52];

void solve() {
	int f,r,i,j,k,l, x,y,z;
	
	cin>>N>>TW>>TC;
	FOR(i,N) {
		cin>>W[i]>>V[i]>>x;
		WW[x-1].push_back(i);
	}
	
	int ma=0,col,w;
	FOR(i,50) {
		for(col=TC;col>=0;col--) {
			memmove(tmp,dpdp[col],sizeof(tmp));
				
			FOR(j,WW[i].size()) {
				int tar=WW[i][j];
				for(w=TW;w>=W[tar];w--) tmp[w]=max(tmp[w],tmp[w-W[tar]]+V[tar]);
			}
			
			for(w=TW;w>=0;w--)
				dpdp[col+1][w] = max(dpdp[col+1][w], tmp[w]);
		}
	}
	
	FOR(i,TC+1) FOR(w,TW+1) ma=max(ma,dpdp[i][w]);
	
	return _P("%d\n",ma);
}

まとめ

うーん、これは単純に自分のDP経験不足だな。
こういうDPの組み方もあるのか。