RUPC (Ritsumeikan University Programming Contest) 2011 Problem E Anipero

問題

イベントにいくつかのアーティストを招待する。

アーティストはシークレットアーティストn組と、通常のアーティスト組に分かれていて、
シークレットアーティストの候補の中から1組または2組を、
通常のアーティストの候補の中からx組以上を招待する必要がある。

それぞれのアーティストを招待するのにかかる費用および、アーティストを招待したときの満足度が与えられる。

費用の和がlimit以下で、かつ上の条件を満たすようなアーティストの選び方のうち、招待したアーティストの満足度の和が最大になるような選び方の、満足度の和を求めよ。

制約条件

n≦100
m≦100
x≦m
limit≦1000
それぞれの費用、満足度≦10

方針

動的計画法による。
まずは通常のアーティストをx組選ぶ選び方を求める。
dp[i][j]を、アーティストをi組選び、そのときの費用の和がjであるようなアーティストの選び方をしたときの、満足度の最大値とする。

この表をアーティストを昇順に、iを降順にまわすループにより更新することで、
dp[i][j]が求まる。

dp2[0][j]を、通常のアーティストをx人以上選び、費用がjかかっているときの満足度の最大値とする。
この表を同じようにシークレットアーティストについて更新することで、シークレットアーティストをi人招待した場合の、費用と満足度の表が得られる。

dp2[i][j]のなかで1≦i≦2かつj≦limitを満たす最大のdp2[i][j]が求める答えである。

int sw[100],sv[100],w[100],v[100];
int dp[103][1001],dp2[3][1001];

int main()
{
	int limit,n,m,x;
	while(cin>>limit>>n>>m>>x,limit){
		string tmp;
		rep(i,n)cin>>tmp>>sw[i]>>sv[i];
		rep(i,m)cin>>tmp>>w[i]>>v[i];
		
		memset(dp,-1,sizeof(dp));
		memset(dp2,-1,sizeof(dp2));
		
		dp[0][0]=0;
		rep(k,m)for(int i=m-1;i>=0;i--)rep(j,1001)if(dp[i][j]>=0){
			if(j+w[k]<=limit)dp[i+1][j+w[k]]=max(dp[i+1][j+w[k]],dp[i][j]+v[k]);
		}
		
		for(int i=x;i<=m;i++)rep(j,1001)dp2[0][j]=max(dp2[0][j],dp[i][j]);
		
		int ans=-1;
		
		rep(k,n)for(int i=1;i>=0;i--)rep(j,1001)if(dp2[i][j]>=0){
			if(j+sw[k]<=limit)dp2[i+1][j+sw[k]]=max(dp2[i+1][j+sw[k]],dp2[i][j]+sv[k]);
		}
		
		rep(i,2)rep(j,1001)ans=max(ans,dp2[i+1][j]);
		cout<<ans<<endl;
	}
	return 0;
}