yukicoder : No.2026 Yet Another Knapsack Problem

思いついてしまえばすんなり。
https://yukicoder.me/problems/no/2026

問題

N種類の品物がある。
i番の品物は、重さがiで個数はC[i]、価値はV[i]とする。

k個の品物を、重さの合計がNとなるように選ぶとき、価値の総和を最大化せよ。

解法

f(n,m,k) := n番目までの品物を、重さの合計がm、個数の合計がkとなるように選んだ時の価値の最大値
とすると、一見状態がO(N^3)あるので、スライド最小値を使ってもTLEする。

ここで、重さが大きい順に考えることにする。
そうすると、n番目以上の品物を考えるときは、個数は高々N/n個まで考えればよい。
結果、考えるべき状態がO(N^2*logN)まで減り、なんとか間に合う。

int N;
int C[2525];
ll V[2525];

ll dp[2525][2525];

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N;
	FOR(i,N) cin>>C[i+1]>>V[i+1];
	FOR(x,2522) FOR(y,2522) dp[x][y]=-1LL<<60;
	dp[0][0]=0;
	for(i=N;i>0;i--) {
		int maxn=N/i;
		
		for(int n=0;n<=maxn;n++) {
			for(int w=0;w<=N;w++) {
				if(n&&w>=i) break;
				deque<pair<int,ll>> Q;
				int cn=n;
				int cw=w;
				while(cn<=maxn&&cw<=N) {
					while(Q.size()&&cn-Q.front().first>C[i]) Q.pop_front();
					ll add=dp[cn][cw]+V[i]*(2500-cn);
					if(Q.size()) {
						dp[cn][cw]=max(dp[cn][cw],Q.front().second-V[i]*(2500-cn));
					}
					while(Q.size()&&Q.back().second<=add) Q.pop_back();
					Q.push_back({cn,add});
					cn++;
					cw+=i;
				}
			}
		}
	}
	
	for(i=1;i<=N;i++) {
		ll ma=-1LL<<60;
		FOR(x,N+1) ma=max(ma,dp[i][x]);
		cout<<ma<<endl;
	}
	
}

まとめ

似たようなテク、どこかで見たような気がするけど思い出せないな…。