uva580Critical Mass

递推。

 

用f[i]代表i个盒子的放法，设g[i]=2^n-f[i]，代表i个盒子不满足条件的放法。

枚举第一个U所在的位置j。则方法有g[j-2]*(2^(i-j-2))种，j-1必须是L。

所以就慢慢递推了。。。

#include<cstdio>

#include<algorithm>

#include<cstring>

using namespace std;

const int maxn = 100 + 10;

int f[maxn],g[maxn];

int n=30;

void init() {

    for(int i=0;i<=2;i++) g[i]=(1<<i)-f[i];

    for(int i=3;i<=n;i++) {

        f[i]=(1<<(i-3));

        for(int j=2;j<=i-2;j++) f[i]+=g[j-2]*(1<<(i-j-2));

        g[i]=(1<<i)-f[i];

    }

}

int main() {

    init();

    while(scanf("%d",&n)==1 && n) printf("%d\n",f[n]);

    return 0;

}