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; }