奇怪的气球膨胀 分治（说白了还是dp?）

【问题描述】

　　一开始有一个红色气球，每小时后，一个红色气球会变成3个红气球和一个蓝气球（蓝气球在2*2的矩阵中的右下角），而一个蓝气球会变成4个蓝气球，如下图所示分别经过0,1,2,3小时后的情况。
　　
　　
　　现在请你计算经过k小时后，第A~B行一共有多少个红气球？

【输入格式】

　　第一行为T，表示测试数据组数。每组数据占一行，包含3个正整数k,A,B（1<=A<=B<=2^k）。

【输出格式】

　　每组数据输出一行，包含一个正整数，表示k小时后A~B行红气球总数。

【输入样例】

3
0 1 1
3 1 8
3 3 7

【输出样例】

1
27
14

【数据范围】

T<1000 0<=k<=30

——————————————————————————————————————————————

容易想到四分棋盘，但是这样有两个比较大的问题：一，代码复杂；二，时间爆炸。（想一下四分棋盘的时候最坏情况分到每个格子上）
所以这个题状态的设计不可以和棋盘有关。

考虑一个很无脑的想法：设f(i,k)表示在第k个小时前i行的红气球总数，那么最后的答案就是f(B,K)-f(A-1,K)。
怎么递归求解f(i,k)呢？
用l[i]表示2^i，c[i]表示3^i。根据题目描述可以发现f(l[k],k)=c[k]。这就是递归的边界条件。不是边界的情况有两种：第一种是棋盘分为上面两个完整的k-1小时后的部分和一个下面的不完整的k-1小时的部分（这个时候把上下两部分交换一下位置是一样的），第二种是棋盘没有被分割。
可以发现对于第一种情况，分割不完整的k-1小时的部分正是对应第二种情况棋盘没有被分割。

这样，状态转移总结为f(i,k)=i > l[k-1] ? f(i-l[k-1],k-1)+c[k-1] * 2 : 2 * f(i,k-1) , f(l[k],k)=c[k];

问题的时间复杂度只和K有关，为O(K)。

AC代码：

#include<iostream>
#include<cstdio>
#include<cstdlib>
using namespace std;
const int maxn=35;
typedef long long LL;

LL c[maxn];
int T,A,B,K,l[maxn];

void ready()
{
    c[0]=1;
    l[0]=1;
    for(int i=1;i<=30;i++)
        c[i]=c[i-1]*3,l[i]=l[i-1]*2;
}
LL solve(int i,int k)
{
    if(i==l[k]) return c[k];
    return i>l[k-1] ? 2*c[k-1]+solve(i-l[k-1],k-1) : solve(i,k-1)*2;
}
int main()
{
    freopen("test.in","r",stdin);
    freopen("test.out","w",stdout);
    ready();
    scanf("%d",&T);
    while(T--)
    {
        scanf("%d%d%d",&K,&A,&B);
        cout<<solve(B,K)-solve(A-1,K)<<endl;
    }
    return 0;
}