yukicoder : No.783 門松計画

今年の門松はまだ優しかったですね。
https://yukicoder.me/problems/no/783

問題

店でN種類の竹が売っており、それぞれ長さL[i]の竹の値段がW[i]である。
それぞれの竹は複数購入することもできる。

予算Cでいくつかの竹を買って横に並べるとき、それらの高さが門松列を満たす並べかたのうち長さの総和の最大値を求めよ。
ただし竹が３本以上ないと門松列とはみなさない。

解法

dp(a,b,c) := 端から２番目の竹の長さがa、端の長さがb、残金cであるときの長さの総和の最大値(ただしa,b=0の場合該当する竹がないことを示す)
とし、dp(0,0,C)=0から順次埋めていこう。

長さa,bの竹の隣に新たな竹を配置するので、(a,b,L[i])が門松列を満たすなら
dp(b,L[i],c-W[i]) = dp(a,b,c)+L[i]
の要領で更新していく。
竹が3本以上ないと門松列とみなさないので、a,bが非0のとき(dp(a,b,c)+L[i])の最大値を覚えるようにするとよい。

int N,C;
int W[51];
int A[51],B[51];
int dp[51][51][51];

int ma;


void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N>>C;
	FOR(i,51) W[i]=51;
	FOR(i,N) cin>>A[i];
	FOR(i,N) cin>>B[i];
	FOR(i,N) W[A[i]]=min(W[A[i]],B[i]);
	
	FOR(x,51) FOR(y,51) FOR(r,51) dp[x][y][r]=-1<<30;
	dp[0][0][C]=0;
	int ma=0;
	for(i=C;i>=0;i--) {
		for(x=0;x<=50;x++) for(y=0;y<=50;y++) {
			for(r=1;r<=50;r++) if(W[r]<=i) {
				if(x==r || y==r) continue;
				if(x&&y&&x<y&&y<r) continue;
				if(x&&y&&x>y&&y>r) continue;
				dp[y][r][i-W[r]]=max(dp[y][r][i-W[r]],dp[x][y][i]+r);
				if(x&&y) {
					
					ma=max(ma,dp[x][y][i]+r);
				}
			}
		}
	}
	
	cout<<ma<<endl;
}

まとめ

わりとオーソドックスなDP。