【CF 676B Pyramid of Glasses】模拟，递归

题目链接：http://codeforces.com/problemset/problem/676/B

题意：一个n层的平面酒杯金字塔，如图，每个杯子的容量相同。现在往最顶部的一个杯子倒 t 杯酒，求流动结束后有多少个杯子被装满。

思路：每个局部的两代三个杯子的流动过程是一致的，因此可以用递归来模拟求解。

具体为：设add(cur, i, l)执行“往第 i 个杯子倒cur量的酒”，附加信息： i 位于第 l 层。若执行完剩余了surplus量的酒，则往 i 的下一层左右两侧的杯子各倒surplus/2量的酒；若无剩余，则抵达递归基。

关于 i 与它下一层的对应关系：我对所有杯子从1开始逐层从左到右编号，因此 i 的左下为i+l, 右下为i+l+1。

关于surplus的值：按照CF的题解的做法，如果有n层，则把每个杯子的容量记为volume = 2 ^ n份，这样能保证即使到第n层每次的cur也都整数。

维护数组v, 其中v[i] 记录当前第 i 个杯子中已有的酒量，若有剩余，则surplus = cur - (volume - v[i])。

最后统计下所有n*(n+1)/2个杯子中v[i]==volume的个数即可。

 1 #include <cstdio>
 2 #include <cmath>
 3 using namespace std;
 4 const int MAX_N = 10;
 5
 6 int t, n;
 7 int num;
 8 int v[MAX_N*(MAX_N+1)/2 + 1];
 9 int volume;
10 int cnt;
11
12 void add(int cur, int i, int l){
13     if(l > n) return ;
14     if(cur + v[i] <= volume){//最多加满当前的，不会溢出
15         v[i] += cur;
16         return ;
17     }
18     int surplus = cur - (volume - v[i]);//有溢出
19     v[i] = volume;
20     add(surplus/2, i+l, l+1);
21     add(surplus/2, i+l+1, l+1);
22 }
23
24 int main()
25 {
26     scanf("%d%d", &n, &t);
27     num = n*(n+1)/2;
28     volume = pow(2, n);
29     int cur = volume * t;
30     cnt = 0;
31     add(cur, 1, 1);
32      for(int i=1; i<=num; i++){
33          //printf("%d %d\n", i, v[i]);
34          if(v[i] == volume) cnt++;
35      }
36     printf("%d\n", cnt);
37     return 0;
38 }