PKU演習問(8/10)

PKU

このままじゃ話にならない。何とかしないと！！

No. 問題名 問題の種類および解法 難易度
2486 Apple Tree 動的計画法（Tree DP+ナップサック問題） ★★★★★
1985 Cow Marathon 動的計画法（Tree DP） ★★★☆☆
2264 Advanced Fruits 動的計画法・バックトラック ★★★☆☆

2486 Apple Tree

問題概要

ノード数nの木の、各ノードにりんごがそれぞれいくつかずつ実っている。
1番のノードから出発して、k回以下、ノードを移動して、そのノードにあるりんごを全て取る。（りんごを取れるのは最初の一回のみ）


取れるりんごの最大の個数を求めよ。
n≦100,k≦200を満たす。

解法

自力で思いついたのはO(n^3k^2）のクソ解法のみ（もちろんTLE）。
ぐぐって見つけた解説を要約すると以下のような感じ。

  • dp2[i][j]に、ノードiを根とする部分木からj歩でとれる最大のりんごの数
  • dp[i][j]に、ノードiを根とする部分木で、最後にiまで戻ってきてj歩でとれる最大のりんごの数

をもっておく。
そして、
dp[i][j]=max{dp[i][k]+dp[子][i-k-2]}および
dp2[i][j]=max{dp[i][k]+dp2[子][i-k-2]}
の関係からテーブルを更新していくことで、O(n^2k^2)の計算量で答えが求まる。らしい。
このDPはナップサック問題的であるらしい。そんな気もするけどあんまりピンと来ないorz

ソースコード
int n,k,rng[100];
vector<vi> e;
bool V[100];
int dp[101][201],dp2[101][201];

void dfs(int c)
{
	V[c]=1;
	fr(it,e[c])if(!V[*it])
	{
		dfs(*it);
		for(int i=k;i>=0;i--)for(int j=0;j<i;j++)
		{
			if(i>=2&&j<=i-2)
			{
				dp[c][i]=max(dp[c][i],dp[c][j]+dp[*it][i-2-j]);
				dp2[c][i]=max(dp2[c][i],dp2[c][j]+dp[*it][i-2-j]);
			}
			if(i>0&&j<k)
				dp2[c][i]=max(dp2[c][i],dp[c][j]+dp2[*it][i-1-j]);
		}
	}
}

int main()
{
	while(~scanf("%d%d",&n,&k))
	{
		rep(i,n)scanf("%d",rng+i);
		e.clear(); e.resize(n);
		rep(i,n-1)
		{
			int a,b; scanf("%d%d",&a,&b);
			a--; b--;
			e[a].pb(b); e[b].pb(a);
		}
		rep(i,n)V[i]=0;
		rep(i,n)rep(j,k+1)dp[i][j]=dp2[i][j]=rng[i];
		dfs(0);
		printf("%d\n",max(dp[0][k],dp2[0][k]));
	}
	return 0;
}

1985 Cow Marathon

問題概要

平面状にn個の牧場があり、m個の道でそれらがつながっている。
道は「牧場Aの特定の方向(N,E,W,S)距離dに牧場B」がある、という形式であたえられる。
このとき、最も遠い二つの牧場間の道程を求めよ。


n,m≦40000かつ、二つの牧場間の道程は一意に定まる。

解法

二つの牧場間の道程が一意に定まるので、与えられるグラフは森。
したがって以下のようなTree DPをすれば解ける。


最も遠い牧場間のペアは、(一番遠い葉)-根-(二番目に遠い葉)の場合と、
間に根を通らないのペアの場合のいずれか。
後者の場合は部分木について再帰することで求められる。


根から出ているノードが2個より少ない場合などの場合分けはしっかりやること。

ソースコード
int n,m;
int e[40000][4],d[40000][4],ne[40000];
bool V[40000];

int dp[40000];
int far(int c)//根から最も遠い葉までの距離を求める
{
	V[c]=1;
	if(dp[c]>=0)return dp[c];
	int ret=0;
	rep(i,ne[c])if(!V[e[c][i]])ret=max(ret,far(e[c][i])+d[c][i]);
	return dp[c]=ret;
}
int rec(int c,int p)
{
	V[c]=1;
	int ret=0,a=-1,b=-1;
	rep(i,ne[c])if(e[c][i]!=p)//根のそれぞれの子から1番遠い葉を調べ、上位二つを覚える
	{
		int t=far(e[c][i])+d[c][i];
		if(a<t)b=a,a=t;
		else if(b<t)b=t;
	}
	ret=max(ret,max(a,0)+max(b,0));
	rep(i,ne[c])if(e[c][i]!=p)ret=max(ret,rec(e[c][i],c));//部分木も探索
	
	return ret;
}
int main()
{
	scanf("%d%d",&n,&m);
	rep(i,n)ne[i]=0,V[i]=0,dp[i]=-1;
	
	rep(i,m)
	{
		int a,b,c; char dm;
		scanf("%d%d%d %c",&a,&b,&c,&dm);
		a--; b--;
		e[a][ne[a]]=b; d[a][ne[a]]=c; ne[a]++;
		e[b][ne[b]]=a; d[b][ne[b]]=c; ne[b]++;
	}
	
	int ans=0;
	rep(i,n)if(!V[i])ans=max(ans,rec(i,i));
	printf("%d\n",ans);
	
	return 0;
}

2264 Advanced Fruits

問題概要

二つの文字列A,Bを部分列として含む長さ最小の文字列Cを出力せよ。
そのような文字列が複数ある場合どれを出力してもよい。


A,Bの長さは100以下である。

解法

動的計画法によりまず共通部分列の長さを求めて、後ろから文字列を構成していく。
動的計画法はマンハッタン距離・最長共通部分列とほぼ同じ。


構成用の配列を持ったほうが実装が楽だったかも。

ソースコード
int a,b;
char A[101],B[101];
int dp[101][101];

int main()
{
	while(~scanf(" %s %s",A,B))
	{
		a=strlen(A); b=strlen(B);
		
		rep(i,a+1)rep(j,b+1)dp[i][j]=inf;
		rep(i,101)dp[0][i]=dp[i][0]=i;
		for(int i=1;i<=a;i++)for(int j=1;j<=b;j++)
		{
			dp[i][j]=min(dp[i][j],dp[i-1][j-1]+(A[i-1]!=B[j-1])+1);
			dp[i][j]=min(dp[i][j],min(dp[i-1][j],dp[i][j-1])+1);
		}
		
		char ans[201];
		int len=dp[a][b]; ans[len]=0;
		while(a||b)
		{
			int c=dp[a][b];
			if(a>0&&b>0&&c==dp[a-1][b-1]+(A[a-1]!=B[b-1])+1)
			{
				if(A[a-1]!=B[b-1])ans[--len]=A[--a],ans[--len]=B[--b];
				else ans[--len]=A[--a],--b;
			}
			else if(a>0&&c==dp[a-1][b]+1)ans[--len]=A[--a];
			else if(b>0&&c==dp[a][b-1]+1)ans[--len]=B[--b];
		}
		printf("%s\n",ans);
	}
	return 0;
}