PKU演習問メモ(7/18) - simezi

No.	問題名	問題の種類および解法	難易度
2250	Compromise	最長共通部分文字列（動的計画法）	★★☆☆☆
2137	Cowties	動的計画法	★★☆☆☆

2250 Compromise

問題概要

二つの文章が与えられる。これらの文章に共通する単語の並び（連続しなくともよい）のうち、語数の大きいものを出力せよ。
答えが複数ある場合どれを出力してもよい。

解法

最長共通部分文字列の問題。
動的計画法を用いる典型問題で、deq notes(右リンク集参照)の解説なんかが解りやすい気がする。

列A,列Bをi個、j個使って得られる最長共通部分列の長さをdp[i][j]とおく。
すると、
dp[i+1][j+1]=max{dp[i][j]+(A[i]==B[i]), dp[i+1][j], dp[i][j+1]}
の漸化式が成り立つ。よってこの式にしたがって動的計画法を書けばよい。
答えの文字列はこの表を逆に辿ることで、復元できる。

ソースコード

int n,m;
int dp[101][101];

int main()
{
	string str;
	while(cin>>str)
	{
		vector<string> w1,w2;
		
		w1.pb(str); while(cin>>str,str!="#")w1.pb(str);
		while(cin>>str,str!="#")w2.pb(str);
		
		n=w1.size(); m=w2.size();
		rep(i,n+1)rep(j,m+1)dp[i][j]=0;
		
		rep(i,n)rep(j,m)
		{
			dp[i+1][j+1]=dp[i][j]+(w1[i]==w2[j]);
			if(dp[i+1][j+1]<dp[i][j+1])dp[i+1][j+1]=dp[i][j+1];
			if(dp[i+1][j+1]<dp[i+1][j])dp[i+1][j+1]=dp[i+1][j];
		}
		vector<string> ans;
		for(int i=n-1,j=m-1;i>=0&&j>=0;)
		{
			if(dp[i+1][j+1]==dp[i][j]+(w1[i]==w2[j]))
			{
				if(w1[i]==w2[j])ans.pb(w1[i]);
				i--; j--;
			}
			else if(dp[i+1][j+1]==dp[i][j+1])i--;
			else j--;
		}
		reverse(all(ans));
		rep(i,ans.size())cout<<ans[i]<<(i==ans.size()-1?"\n":" ");
	}
	
	return 0;
}

2137 Cowties

問題概要

n匹の牛がいる。n匹の牛はそれぞれs[i]種類の候補地のどこかにいなければならない。
牛ごとに各候補地の座標が与えられたとき、
0番目の牛-1番目の牛-…-n-1番目の牛-0番目の牛と、輪を作って牛を紐で結ぶために必要な最小の紐の長さを求めよ。

n≦100,s[i]≦40とする。

解法

0番目の牛をどこに置くかが決まっていれば、以下のような動的計画法によりO(ns^2)で解が求められる。なので、最初の牛の置き方をs[0]通り試せばよい。

動的計画法：
dp[i][j]に牛iがj番目の候補地にいるときの、i番目までの牛を結ぶのに必要な紐の長さとすれば、
dp[i+1][j]=min｛dp[i][k]+(牛iの候補地kと、牛i+1のjの候補地の距離)｝
の漸化式が成り立つのでコードにすればよい。

小数点以下は単に切り捨てれば良いようである（それで数回はまった）

ソースコード

int n,k[100];
vi X[100],Y[100];
double dp[100][40];

double D(int a,int b,int c,int d)
{
	return hypot(X[a][b]-X[c][d],Y[a][b]-Y[c][d]);
}

double solve(int a)
{
	rep(i,n)rep(j,40)dp[i][j]=INF;
	dp[0][a]=0;
	for(int i=1;i<n;i++)
	{
		rep(j,k[i-1])rep(l,k[i])
		dp[i][l]=min(dp[i][l],dp[i-1][j]+D(i-1,j,i,l));
	}
	double ret=INF;
	rep(i,k[n-1])ret=min(ret,dp[n-1][i]+D(0,a,n-1,i));
	return ret;
}

int main()
{
	scanf("%d",&n);
	rep(i,n)
	{
		X[i].clear(); Y[i].clear();
		scanf("%d",k+i);
		int a,b;
		rep(j,k[i])scanf("%d%d",&a,&b),X[i].pb(a),Y[i].pb(b);
	}
	
	double ans=INF;
	rep(i,k[0])ans=min(ans,solve(i));
	printf("%d\n",int(ans*100));
	
	return 0;
}