PKU演習問メモ(4/8 part2)

PKU
No. Title 分類・解法
1260 Pearls Dynamic programming
1384 Piggy-Bank Knapsack problem, Dynamic programming
1466 Girls and Boys Minimum vertex cover in bipartite graph

眠くてノルマがきつい……
おまけにCodeforcesのラウンド出て明日の授業大丈夫だろうかｗ

1260 Pearls

問題概要

c種類の価格の異なる真珠がある。価格p[i]の真珠をn個買うにはp[i]*(n+10)円必要である。
ある真珠はより高い真珠で置き換えても良いとするとき、c種類の真珠を与えられた個数だけ買うのに必要な最小の金額を求めよ。

解法

高い真珠を纏め買いすると安い真珠をいくつか買うよりも安くなるかも、という問題。
1〜i番目の種類までの真珠の買い方の最適解から、i+1番目の真珠の最適解が求まることに注目して動的計画法を使うと良い。


下のコードにおいてcost[j][i]はj番目からi番目の真珠をi番目の値段で纏め買いするときにかかる金額である。

ソースコード
int c;
int n[100],p[100];
int dp[100],sum[100][100];

int main()
{
	int cs; cin>>cs;
	while(cs--)
	{
		cin>>c;
		rep(i,c)cin>>n[i]>>p[i],dp[i]=inf;
		
		rep(i,c)rep(j,i+1)
		{
			cost[j][i]=10;
			for(int k=j;k<=i;k++)cost[j][i]+=n[k];
			cost[j][i]*=p[i];
		}
		
		dp[0]=p[0]*(n[0]+10);
		for(int i=1;i<c;i++)
		{
			dp[i]=cost[0][i];
			rep(j,i)dp[i]=min(dp[i],dp[j]+cost[j+1][i]);
		}
		
		while(c>0&&n[c-1]==0)c--;
		cout<<(c?dp[c-1]:0)<<endl;
	}
	return 0;
}

1384 Piggy-Bank

問題概要

重さEの貯金箱に、重さがちょうどFになるようにコインを入れるとき、入れるコインの額の最小値を求めよ。

解法

ナップサック問題。貯金箱がaグラムになるような入れ方は、a-p[i]グラムのときにw[i]のコインを入れる入れ方という関係式を使って動的計画法。

ソースコード
int n,p[500],w[500];
int dp[10001];

int main()
{
	int cs; cin>>cs;
	while(cs--)
	{
		int e,f,n; cin>>e>>f>>n; f-=e;
		rep(i,n)cin>>p[i]>>w[i];
		
		fill(dp,dp+f+1,inf);
		dp[0]=0;
		rep(j,10001)rep(i,n)if(j>=w[i])
			dp[j]=min(dp[j],dp[j-w[i]]+p[i]);
		
		if(dp[f]!=inf)
			cout<<"The minimum amount of money in the piggy-bank is "
				<<dp[f]<<"."<<endl;
		else cout<<"This is impossible."<<endl;
	}
	return 0;
}

1466 Girls and Boys

問題概要

n人の生徒の「気になる異性」のリストが与えられるとき、気になる異性のペアが一組もないようなグループをつくるとき、その最大人数を求めよ。

解法

ホモセクシャルな個体は居ないと仮定しておkらしい。
最初に生徒の性別を決めていく。

問題は要は二部グラフの最小点カバーであるので、最大マッチングに等価。
なので性別を決定したら二部グラフの最大マッチングを求めていく。

ソースコード
int n;
bool e[500][500],male[500];

int p[500];
bool V[500];

bool rec(int s)
{
	if(s<0)return 1;
	rep(i,n)if(e[s][i]&&!V[i])
	{
		V[i]=1;
		if(rec(p[i]))return p[s]=i,p[i]=s,1;
	}
	return 0;
}
void ck(int c,int s)
{
	V[c]=1; male[c]=s;
	
	rep(i,n)if(e[c][i]&&!V[i])ck(i,s^1);
}

int main()
{
	while(~scanf("%d",&n))
	{
		rep(i,n)
		{
			male[i]=0;
			rep(j,n)e[i][j]=0;
		}
		
		int t,k;
		rep(i,n)
		{
			scanf("%d: (%d)",&t,&k);
			rep(j,k)
			{
				int t;
				scanf("%d",&t),e[t][i]=e[i][t]=1;
			}
		}
		
		fill(V,V+n,0);
		rep(i,n)if(!V[i])ck(i,0);
		
		int ans=n; fill(p,p+n,-1);
		rep(i,n)if(male[i])
		{
			fill(V,V+n,0); V[i]=1;
			if(rec(i))ans--;
		}
		cout<<ans<<endl;
	}
	return 0;
}