PKU演習問メモ(10/23)

PKU

毎日少しずつ解けるよう頑張る。

No. 問題名 問題の種類および解法 難易度
1179 Polygon 動的計画法 ★★☆☆☆
1144 Network 関節点（グラフ） ★★★☆☆

1179 Polygon

問題概要

n角形の形をしたグラフが与えられる。
各頂点には数が、辺には'+'または'*'の演算子が書かれている。


このグラフに次のような操作を施す。

  • 一つの辺を選び、削除する
  • 以下次の操作を頂点が最後の一つになるまで繰り返す
    • 一辺およびその両端の２頂点の組を選ぶ
    • その組を、(左の数) 演算子 (右の数）の数が書かれた頂点に置き換える

このとき、最後に得られる最大の数および、そのような操作の最初に選ぶ辺として可能なものを全て求めよ。

解法

典型的な動的計画法問題。
辺と頂点を置き換える操作は、a1+a2*a3+a4*a5...のような式に括弧を入れていくことに相当する。
最初の辺の削除は、式の先頭を何処にするか決定することになる。


したがって最初の項をn通り決めて、それぞれに対してdp[i][j]にi番目からj番目の項を使って出来る最大の数を入れて、更新していくことが思いつく……が、入力に負の数がありうるため、最小の数も覚えなければならない。
dp[i][j]に最小の数、DP[i][j]に最大の数を覚えたのが下のコード。
ループではなくメモ化再帰で書いたコードはTLEだった。

ソースコード
const ll INF=1LL<<60;

int n,d[50];
char o[50];
ll dp[50][50],DP[50][50];

ll solve()
{
	rep(i,n)rep(j,n)dp[i][j]=INF,DP[i][j]=-INF;
	rep(i,n)dp[i][i]=DP[i][i]=d[i];
	
	rep(len,n)rep(l,n-len)
	{
		int r=l+len;
		for(int m=l;m<r;m++)
		{
			ll a=dp[l][m],b=dp[m+1][r],A=DP[l][m],B=DP[m+1][r];
			ll c,d,e,f;
			if(o[m]=='t')c=a+b,d=A+b,e=a+B,f=A+B;
			else c=a*b,d=A*b,e=a*B,f=A*B;
			dp[l][r]=min(dp[l][r],min(min(c,d),min(e,f)));
			DP[l][r]=max(DP[l][r],max(max(c,d),max(e,f)));
		}
	}
	return DP[0][n-1];
}
int main()
{
	scanf("%d",&n);
	rep(i,n)scanf(" %c %d",o+i,d+i);
	
	ll mx=-INF,ans[50]; int na=0;
	rep(i,n)
	{
		rotate(o,o+1,o+n);
		ll t=solve();
		if(t>mx)mx=t,na=0;
		if(t==mx)ans[na++]=i+1;
		rotate(d,d+1,d+n);
	}
	
	cout<<mx<<endl;
	rep(i,na)cout<<ans[i]<<(i==na-1?'\n':' ');
	return 0;
}

1144 Network

問題概要
解法

求めるものはグラフの関節点である。
深さ優先探索を使い関節点を求めるアルゴリズムがあるらしい。
……未解読なので後で解読したらここに書く。

ソースコード

spaghetti source（関節点（http://www.prefield.com/algorithm/graph/bridge.html））のコードを使用

int main()
{
	int n;
	while(cin>>n,n)
	{
		cin.ignore();
		Graph g(n);
		while(1)
		{
			string str; getline(cin,str);
			stringstream ss(str); int s,t;
			ss>>s; if(s==0)break;
			s--;
			while(ss>>t)
			{
				t--;
				g[s].pb(Edge(s,t,0)); g[t].pb(Edge(t,s,0));
			}
		}
		vi art;
		articulationPoint(g,art);
		sort(all(art)); art.erase(unique(all(art)),art.end());
		cout<<art.size()<<endl;
	}
	return 0;
}