yukicoder : No.1583 Building Blocks

これは典型かな。
https://yukicoder.me/problems/no/1583

問題

N個の積み木がある。
それぞれの重さW[i]と硬さS[i]が与えられる。

このうちのいくつかを縦に積み重ねることを考える。
各積み木の上に重なる積み木群の重さ、自身の硬さ以下でなければならない。

最大何個積み重ねることができるか。

解法

2つの積み木i,jがあったとき、どちらが上であるとよいか考える。
もしその上に総重量wだけ積み木があるとする。

• iが上の時、w≦S[i]かつw+W[i]≦S[j]ならよい
• jが上の時、w≦S[j]かつw+W[j]≦S[i]ならよい

右の式を考えると、W[i]+S[i]の総和が小さいもの程上に置く方が良い。
これで置く順序は確定したので、あとは積み木番号と積み重ねた個数に対する総重量の最小値を状態として、O(N^2)のDPで処理することができる。

int N;
ll W[1010],S[1010];
pair<int,int> P[1010];

ll dp[1010];

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N;
	FOR(i,N) {
		cin>>W[i]>>S[i];
		P[i]={W[i]+S[i],i};
	}
	sort(P,P+N);
	
	FOR(x,N+1) dp[x]=1LL<<60;
	dp[0]=0;
	int ma=0;
	FOR(i,N) {
		x=P[i].second;
		for(j=N-1;j>=0;j--) {
			if(dp[j]<=S[x]) {
				dp[j+1]=min(dp[j+1],dp[j]+W[x]);
			}
		}
	}
	FOR(j,N+1) if(dp[j]<1LL<<60) ma=j;
	cout<<ma<<endl;
	
	
}

まとめ

最近似た問題見た気がするな。