1252 Euro Efficiency

問題概要

6種類のコインの価値が与えられる。
このとき1〜100の値段を支払うのに使うコインの最小の枚数の平均値を求めよ。

ただし支払いに使うコインの枚数は、こちらが渡すコインの枚数と、おつりで貰うコインの枚数の和を表すものとする。

解法

金額xをつくるコインの最小枚数は最初にdpで求める。
金額xの支払いのコインの最小枚数は、i=x〜3000くらいを動かして、
支払う枚数+おつりの枚数の最小値を探索する。

ソースコード

int n,c[6],dp[3001],dp2[101];

int main()
{
	scanf("%d",&n);
	rep(i,n)
	{
		rep(j,6)scanf("%d",c+j);
		rep(j,3001)dp[j]=dp2[j]=inf; dp[0]=0;
		
		rep(j,3001)rep(k,6)if(j+c[k]<3001)dp[j+c[k]]=min(dp[j+c[k]],dp[j]+1);
		rep(j,101)for(int k=j;k<3001;k++)dp2[j]=min(dp2[j],dp[k]+dp[k-j]);
		
		int s=accumulate(dp2+1,dp2+101,0),m=*max_element(dp2+1,dp2+101);
		printf("%.2f %d\n",s/100.0,m);
	}
	
	return 0;
}