PKU演習問メモ(8/5) - simezi

No.	問題名	問題の種類および解法	難易度
2923	Relocation	ビットDP・ビットでの部分集合列挙	★★★★☆
3356	AGTC	動的計画法（編集距離）	★★☆☆☆
2241	The Tower of Babylon	メモ化再帰	★★☆☆☆
2663	Tri Tiling	動的計画法	★★★☆☆
2353	Ministry	動的計画法・バックトラック	★★★☆☆

2923 Relocation

問題概要

2台の車を使ってn個の荷物を運ぶ。それぞれの車の積載可能な荷物の量はC1,C2で、n個の荷物の重さはそれぞれw[i]で与えられる。

2台の車は常に一緒に移動するとするとき、全ての荷物を移動させるのに必要な最小の往復回数を求めよ。車で運べないような荷物はないものと仮定してよい。
n≦10,
w[i],C1,C2≦100を満たす。

解法

荷物の数は最大10個と少ないので、ビットDPができる。
整数bitのi番目のビットがオンであることをi番目の荷物がまだ運ばれてない状態に対応させ、
dp[bit]のテーブルを持つ。bitの一部の荷物を運んだ状態をnbitとすると、
dp[nbit]=min(dp[nbit],dp[bit]+1)の漸化式が成り立つため、それをコードにすればよい。

制限時間がやや厳しいので、先にその荷物の集合が運び出せるかを表にして持っておくとよい。
ビットでの部分集合の列挙にはつい先日のSRMのコードが利用できる。

ソースコード

int n,c1,c2,w[10];
int dp[1024];
bool ok[1024];//ビットで表した荷物の集合が運び出せるか

int main()
{
	int CS; cin>>CS;
	rep(cs,CS)
	{
		cin>>n>>c1>>c2;
		rep(i,n)cin>>w[i];
		
		if(c1<c2)swap(c1,c2);
		
		rep(i,1<<n)ok[i]=0;
		rep(i,1<<n)for(int j=i;j>0;j=(j-1)&i)
		{
			int s1=0,s2=0;
			rep(k,n)if(1<<k&i)
			{
				if(1<<k&j)s1+=w[k];
				else s2+=w[k];
			}
			if(s1<s2)swap(s1,s2);
			if(s1<=c1&&s2<=c2)
			{
				ok[i]=1; break;
			}
		}
		
		rep(i,1<<n)dp[i]=inf;
		dp[(1<<n)-1]=0;
		for(int i=(1<<n)-1;i>0;i--)for(int j=i;j>0;j=(j-1)&i)
		if(ok[j])dp[i^j]=min(dp[i^j],dp[i]+1);
		
		cout<<"Scenario #"<<cs+1<<":"<<endl<<
			dp[0]<<endl<<endl;
	}
	return 0;
}

3356 AGTC

問題概要

二つの文字列のレーベンシュタイン距離を求めよ。

解法

定石にしたがって動的計画法。
すなわち、文字列Aの先頭からi文字と文字列Bの先頭からj文字の編集距離をdp[i][j]とすれば、
dp[i+1][j+1]=min{dp[i][j]+(A[i]!=B[j]),dp[i+1][j]+1,dp[i][j+1]+1}
の関係が成り立つため、それをコードにすればよい。

LCS（最長共通部分列）とは漸化式が微妙に異なるので注意。
なお、問題文のどこにも書かれていないが、入力ケースは複数与えられる。

ソースコード

int n,m; char a[1001],b[1001];
int dp[1001][1001];

int main()
{
	while(~scanf("%d %s %d %s",&m,a,&n,b))
	{
		rep(i,m+1)rep(j,n+1)dp[i][j]=inf;
		rep(i,1001)dp[0][i]=dp[i][0]=i;
		
		for(int i=1;i<=m;i++)
		for(int j=1;j<=n;j++)
		{
			dp[i][j]=min(dp[i][j],dp[i-1][j-1]+(a[i-1]!=b[j-1]));
			dp[i][j]=min(dp[i][j],dp[i-1][j]+1);
			dp[i][j]=min(dp[i][j],dp[i][j-1]+1);
		}
		printf("%d\n",dp[m][n]);
	}
	return 0;
}

2241 The Tower of Babylon

問題概要

n（≦30）種類の直方体があり、それぞれの各辺の長さはx[i],y[i],z[i]で与えられる。
いま、これらの直方体を以下の条件を満たすように積み上げるとき、積み上げることのできる最大の高さを求めよ。

条件:
i番目の直方体の真上にj番目の直方体が乗っているとすると、
x[i]＞x[j],y[i]＞y[j]

なお、全ての直方体はx,y,zを任意に入れ替えてよい。

解法

現在の上に来ている面を各辺が長さa,bの長方形とする。
このときの最適解をdp[(a,b)]とすればメモ化再帰できる。
向きは任意に入れ替え可能なので、next_permutationなどを使うと楽。

ソースコード

int n,l[30][3];
map<pi,int> dp;

int rec(int a,int b)
{
	if(b>a)swap(a,b);
	if(dp.count(mp(a,b)))return dp[mp(a,b)];
	
	int o[]={0,1,2},ans=0;
	do rep(i,n)
	{
		if(a>l[i][o[0]]&&b>l[i][o[1]])
		{
			ans=max(ans,rec(l[i][o[0]],l[i][o[1]])+l[i][o[2]]);
		}
	}while(next_permutation(o,o+3));
	return dp[mp(a,b)]=ans;
}

int main()
{
	int cs=0;
	while(scanf("%d",&n),n)
	{
		dp.clear();
		int mx=0;
		rep(i,n)
		{
			scanf("%d%d%d",l[i],l[i]+1,l[i]+2);
			rep(j,3)mx=max(mx,l[i][j]);
		}
		printf("Case %d: maximum height = %d\n",++cs,rec(mx+1,mx+1));
	}
	return 0;
}

2663 Tri Tiling

問題概要

3xnの長方形に、1x2のドミノを隙間なく敷き詰める場合の数を求めよ。
0≦n≦30である。

解法

一列の状態としてありうるのは2^3=8通り。
したがって、i列目までを、i列目の状態をj（0≦j＜8）で敷き詰める場合の数をdp[i][j]として動的計画法をすればよい。

最も右の列の敷き詰め方は以下の場合がある。

1x2の隙間に縦にドミノを敷く
全ての隙間に横にドミノを敷く

答えは32bit整数に収まるので特に工夫は必要ない。

ソースコード

int n;
int dp[32][8];

int main()
{
	rep(i,32)rep(j,8)dp[i][j]=0;
	dp[0][0]=1; dp[1][0]=1;
	for(int i=1;i<31;i++)rep(j,8)
	{
		rep(k,2)if(!(j&1<<k)&&!(j&1<<k+1))dp[i][j|1<<k|1<<k+1]+=dp[i][j];
		dp[i+1][j^7]+=dp[i][j];
	}
	
	while(cin>>n,~n)cout<<dp[n][8]<<endl;
	return 0;
}

2353 Ministry

問題概要

M階立てで、各フロアにN個の部屋のあるビルのM階に閣僚がいる。閣僚に書類にサインさせたいが、閣僚はM階の役人が最低一人書類にサインしないとサインをしない。
更に、役人は下の条件を一つ以上満たさないとサインをしない。

1階の役人であること
1つ下の、同じ部屋番号の部屋の役人がサインしていること
同じ階の、部屋番号が1だけ異なる部屋の役人がサインしていること

i階のj番の部屋の役人がサインするのに支払われる給料が与えられるとき、
最も安く閣僚にサインさせるための書類が通る経路を出力せよ。

M≦100,N≦500を満たす。
また、閣僚が書類をサインするのにかかる給料の合計の最小値は10^9を超えない。

解法

動的計画法による。
i階j番の部屋に書類がつくのにかかる最小の費用をdp[i][j]とすれば、
dp[i][j]は

min{dp[i-1][j],dp[i][j-1],dp[i][j+1]}+(その部屋の役人の給与)

となる。
ただし、配列の更新順には注意する必要がある。

また。i,jに書類がどこから来たかをprev[i][j]として持っておけば、ゴールから逆にたどることで書類の経路を復元できる。

ソースコード

const int inf=1+(int)1e9;

int h,w,fee[100][500];
int dp[100][500],prev[100][500];
int ans[50000],len;

int main()
{
	scanf("%d%d",&h,&w);
	rep(i,h)rep(j,w)scanf("%d",fee[i]+j),dp[i][j]=inf;
	
	rep(i,w)dp[0][i]=fee[0][i];
	for(int i=1;i<h;i++)
	{
		rep(j,w)if(dp[i][j]>dp[i-1][j]+fee[i][j])
			dp[i][j]=dp[i-1][j]+fee[i][j],prev[i][j]=-1;
		
		for(int j=1;j<w;j++)if(dp[i][j]>dp[i][j-1]+fee[i][j])
			dp[i][j]=dp[i][j-1]+fee[i][j],prev[i][j]=-2;
		
		for(int j=w-2;j>=0;j--)if(dp[i][j]>dp[i][j+1]+fee[i][j])
			dp[i][j]=dp[i][j+1]+fee[i][j],prev[i][j]=2;
	}
	int y=h-1,x=min_element(dp[h-1],dp[h-1]+w)-dp[h-1];
	len=0; ans[len++]=x+1;
	while(y>0)
	{
		if(prev[y][x]==-2)x--;
		else if(prev[y][x]==2)x++;
		else if(prev[y][x]==-1)y--;
		ans[len++]=x+1;
	}
	rep(i,len)printf("%d\n",ans[len-i-1]);
	
	return 0;
}