danihao123

搜索

音乐播放器

RSS

RSS Link

计数器

29170

[CF 676B]Pyramid of Glasses

2016年7月31日 12:07 | Comments(0) | Category:题解 | Tags:

这题可以直接模拟,貌似也可过。但复杂度很高。

我们可以直接把t个单位的酒放入第一个杯,然后向下溢出,以此类推,这样复杂度就很优秀了。

代码:

#include <iostream>
using namespace std;
const int maxn=12;
int n;
long double k[maxn][maxn];
int call(int x){
	int i,ans=0;
	long double temp;
	if(x>n)
		return 0;
	for(i=1;i<=n;i++){
		if(k[x][i]>=1.0){
			ans++;
			if(k[x][i]>1.0 && x<n){
				temp=(k[x][i]-1.0)/2;
				k[x][i]=1.0;
				k[x+1][i]+=temp;
				k[x+1][i+1]+=temp;
			}
		}
	}
	return ans+call(x+1);
}
int main(){
	cin>>n>>k[1][1];
	cout<<call(1)<<endl;
	return 0;
}