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番目の町で働く時の収入が与えられたとき、得られる最大の収入を求めよ。
ソースコード
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; }