PKU演習問メモ(7/30)

No. 問題名 問題の種類および解法 難易度
3257 Cow Roller Coaster 動的計画法 ★★★☆☆
3230 Travel 動的計画法 ★★☆☆☆

3257 Cow Roller Coaster

問題概要

全長Lの(一次元の)ジェットコースターを、N個のユニットを使い、B以下の予算で作りたい。


N個のユニットは、それぞれ開始位置がX[i]でなければならない。
N個のユニットの長さW[i],面白さF[i],値段C[i]が与えられたとき、条件を満たすようなコースターのうち、面白さを最大にするものの、面白さを求めよ。


N≦10000,Xi≦1000,Ci≦1000を満たす。

解法

位置iまでで、残り予算jのコースターの面白さの最大値をdp[i][j]として動的計画法
Nが多かったので、コースターを開始位置でソートして、使うコースターを探すときに二分探索をした。

ソースコード
struct S{
	int x,w,f,c;
	bool operator<(const S &r)const{
		return x<r.x;
	}
};

int l,n,b,X[10000];
S coaster[10000];
int dp[1001][1001];

int main()
{
	scanf("%d%d%d",&l,&n,&b);
	rep(i,n){
		int p,q,r,s;
		scanf("%d%d%d%d",&p,&q,&r,&s);
		coaster[i].x=p; coaster[i].w=q;
		coaster[i].f=r; coaster[i].c=s;
	}
	sort(coaster,coaster+n);
	rep(i,n)X[i]=coaster[i].x;
	
	rep(i,l+1)rep(j,b+1)dp[i][j]=-inf;
	dp[0][b]=0;
	rep(i,l)rep(j,b+1)if(dp[i][j]!=-inf)
	{
		int p=lower_bound(X,X+n,i)-X;
		if(p<0||p>=n)continue;
		
		for(;p<n&&X[p]==i;p++)if(j>=coaster[p].c)
		dp[i+coaster[p].w][j-coaster[p].c]=max(dp[i+coaster[p].w][j-coaster[p].c],
			dp[i][j]+coaster[p].f);
	}
	int ans=*max_element(dp[l],dp[l]+b+1);
	printf("%d\n",ans==-inf?-1:ans);
	
	return 0;
}

3230 Travel

問題概要

n個の町でm日間移動しながら働き、得られる収入を最大化したい。
1日ごとに、その町に留まって働くか、別の町へ移動して働くかを選択することができる。


町iからjへ行くコスト(i=jの場合その町に滞在するコスト)、i日目にj番目の町で働く時の収入が与えられたとき、得られる最大の収入を求めよ。

解法

動的計画法による。
i日目にj番目の町に居るときの収入の最大値をdp[i][j]としておけば、

  • 移動する場合
  • しない場合

に分けてそれぞれ漸化式が立つので、それをコードにすればよい。

ソースコード
int n,m;
int in[100][100],cost[100][100];
int dp[101][100];

int main()
{
	while(scanf("%d%d",&n,&m),n)
	{
		rep(i,n)rep(j,n)scanf("%d",cost[i]+j);
		rep(i,m)rep(j,n)scanf("%d",in[i]+j);
		
		rep(i,m+1)rep(j,n)dp[i][j]=-inf;
		dp[0][0]=0;
		
		rep(i,m)rep(j,n)if(dp[i][j]!=-inf)
		{
			rep(k,n)
			dp[i+1][k]=max(dp[i+1][k],dp[i][j]+in[i][k]-cost[j][k]);
		}
		
		int ans=*max_element(dp[m],dp[m]+n);
		printf("%d\n",ans);
	}
	return 0;
}