PKU演習問メモ(8/8)

WAおおすぎ解くの遅すぎ……orz

No. 問題名 問題の種類および解法 難易度
1925 Spiderman 動的計画法 ★★★☆☆
1848 Tree 動的計画法(Tree DP) ★★★★☆
1837 Balance 動的計画法 ★★★☆☆

1925 Spiderman

問題概要

n個のビルがある。それぞれのビルは数直線上に立っている線分とみなす。
各ビルのX[i]座標および高さY[i]が与えられる。


0番のビルからn-1番のビルへ次のような移動を繰り返すことにより移動する。

  • 自分よりX座標の大きいビルへ糸をかける
  • ふりこのようにビルに関して対称な点へ移動する
  • その瞬間に新たなビルに糸をかける

ただし、ふりこ運動をする際に地面に着くような(糸の長さがビルの高さよりも長くなる)移動はできない。


このとき糸を出す最小の回数を求めよ。


X[i],Y[i]≦1000000を満たす。ビルはそのX座標の小さい順に並んでおり、
同じX座標に二つのビルがあることはない。

解法

まず、移動中のY座標は全て同じなので、X座標のみを考えればよい。
全てのビルの座標は1000000以下の整数であるため、dp[i]に座標(i,Y[0])にたどり着くための最小の糸を出す回数を持っておき、各ビルによりテーブルを順次更新していけば、動的計画法ができる。

ソースコード
int n,X[5000],Y[5000];
int dp[1000001];

int main()
{
	int cs; scanf("%d",&cs);
	while(cs--)
	{
		scanf("%d",&n);
		rep(i,n)scanf("%d%d",X+i,Y+i);
		fill_n(dp,1000001,inf);
		dp[X[0]]=0;
		
		int ans=inf;
		for(int i=1;i<n;i++)
		{
			int d=(int)sqrt(Y[0]*(2.0*Y[i]-Y[0]));
			for(int j=1;j<=d;j++)
			if(X[i]-j>=X[0]&&dp[X[i]-j]!=inf)
			{
				if(X[i]+j>=X[n-1])ans=min(ans,dp[X[i]-j]+1);
				else dp[X[i]+j]=min(dp[X[i]+j],dp[X[i]-j]+1);
			}
		}
		printf("%d\n",ans==inf?-1:ans);
	}
	return 0;
}

1848 Tree

問題概要

木が与えられる。
木にエッジを何本か足して、グラフの全てのノードがちょうど1つの閉路に属しているようにしたい。
加えるエッジの最小本数を求めよ。


n≦100を満たす。

解法

なんかTopCoderぽい問題。
ある部分木以下で作る閉路に着目したとき、閉路の作り方は(部分木の)根を含む場合のみを考えればよい。(全てのノードは必ずどこかの閉路に含まれるため)
これで出来た閉路を取り除くと、残りの森について同様の問題ができる。
したがって再帰により解くことができる。


メモ化したのだが解法の計算量がわからない。O(n^3)?

ソースコード
int n,p[100];
vector<vi> e,child;

int dp[100];

void makep(int c)//ノードの親の表を作る
{
	fr(i,e[c])if(p[*i]==-1)p[*i]=c,makep(*i);
}
void makec(int c)//ノードの子孫のリストを作る
{
	child[c].pb(c);
	fr(i,e[c])if(*i!=p[c])
	{
		makec(*i);
		fr(j,child[*i])child[c].pb(*j);
	}
}
int rec(int c)
{
	if(dp[c]>=0)return dp[c];//メモ化
	
	int ret=inf;
	rep(i,child[c].size())rep(j,i)//部分木の閉路なので、子のうち二つを結ぶ
	{
		int x=child[c][i],y=child[c][j];
		if(p[x]==y||p[y]==x)continue;//新しく加えようとする辺が、既にある
		
		bool V[100]={0},fail=0; V[c]=1;
		for(int a=x;a!=c;a=p[a])V[a]=1;
		for(int a=y;a!=c;a=p[a])if(V[a])
		{
			fail=1; break;//閉路が部分木の根を通っていない場合は考えない
		}else V[a]=1;
		if(fail)continue;
		
		int tmp=1;
		rep(k,child[c].size())if(!V[child[c][k]]&&V[p[child[c][k]]])
		{
			tmp+=rec(child[c][k]);
			tmp=min(tmp,inf);
		}
		ret=min(ret,tmp);
	}
	return dp[c]=ret;
}

int main()
{
	scanf("%d",&n);
	e.resize(n); child.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)p[i]=dp[i]=-1;
	p[0]=0; makep(0); p[0]=-1;//親の表を作る
	makec(0);//子孫のリストを作る
	
	int ans=rec(0);
	printf("%d\n",ans==inf?-1:ans);
	
	return 0;
}

1837 Balance

問題概要

腕の重さの無視できる天秤がある。
天秤にはC箇所錘をぶら下げるところがあって、そこにG個の錘を全て使って天秤を水平にしたい。

C個のそれぞれの位置と、G個の錘のそれぞれの重さが与えられたとき、天秤をつりあわせるような錘の配置の場合の数を求めよ。

G≦20,C≦20かつ
全ての錘の重さは25以下の整数、錘を下げる位置は-15から15の整数である。

解法

dp[i]を、天秤の両辺のモーメントの差がiであるような場合の数とする。
錘を一つずつ見ていけば、dpの配列を更新していくことができ、全体でO(CGW)の計算量で
場合の数を求めることが出来る。

ソースコード
int c,g,p[20],w[20];
ll dp[2][8000];

int main()
{
	scanf("%d%d",&c,&g);
	rep(i,c)scanf("%d",p+i);
	rep(i,g)scanf("%d",w+i);
	
	int mn=0,mx=0,cur=0,next=1;
	dp[0][4000]=1;
	rep(i,g)
	{
		for(int j=mn+p[0]*w[i];j<=mx+p[c-1]*w[i];j++)dp[next][j+4000]=0;
		for(int j=mn;j<=mx;j++)if(dp[cur][j+4000])rep(k,c)
		{
			int d=w[i]*p[k];
			dp[next][j+d+4000]+=dp[cur][j+4000];
		}
		mx+=p[c-1]*w[i]; mn+=p[0]*w[i];
		swap(cur,next);
	}
	printf("%lld\n",dp[cur][4000]);
	
	return 0;
}