UVA - 12627 Erratic Expansion : 递归

题目点此跳转

思路

 题目意思是(书上原话)一开始有一个红气球。每小时后,一个红气球会变成3个红气球和一个蓝气球,一个蓝气球会变成4个蓝气球,如图所示分别是经过0, 1, 2, 3小时后的情况。经过k小时后,第A~B行一共有多少个红气球?例如,k=3,A=3,B=7,答案为14。

需要设出如下变量:

g(k, i): k 小时后最下面 i 行的红气球总数
c(k): k 小时后红气球的总数

则对于输入的k, a, b, 显然结果为

g(k, 2k−a+1 ) - g(k, 2k - b)
//即k时从第a行到最后一行的红气球数 - 从第b+1行到最后一行的红气球数

那么只要知道如下递推关系即可解决本题:

g(k, i) = 2 * g(k-1, i-2k−1 ) + c(k), {i>=2k−1}
g(k, i) = g(k-1, i ), {i<2k−1}
c(k) = 3k

代码

LL k, a, b, c[maxn];

LL g(LL k, LL i) {
    if(i == 0) return 0;
    if(k == 0) return 1;
    LL t = 1<<(k-1);
    if(i >= t) return 2*g(k-1, i-t) + c[k-1];
    return g(k-1, i);

}

int main() {

    c[0] = 1;
    for(int i = 1; i <= 30; ++i) c[i] = 3*c[i-1];
    int kase = 0, t; cin >> t;
    while(t--) {
        scanf("%lld%lld%lld", &k, &a, &b);
        LL n = 1<<k;
        printf("Case %d: %lld\n", ++kase, g(k, n-a+1)-g(k, n-b));

    }
    return 0;
}