题意：
有两种盒子分别装有铀(U)和铅(L)，现在把n个盒子排成一列(两种盒子均足够多)，而且要求至少有3个铀放在一起，问有多少种排放方法。
分析：
n个盒子排成一列，共有2n中方案，设其中符合要求的为f(n)种。
f(n)可由下面两种情况递推出来：
- 前n-1个盒子的摆放满足要求，则第n个盒子可以摆放U也可以摆放L，共有2×f(n-1)中方案
- 前n-1个盒子不满足要求，要使前n个盒子满足要求，则第n-2、n-1、n个盒子一定是U。又因为前面的假设，所以第n-3个盒子一定是L(否则前n-1个盒子满足要求了)。所以我们确定最后四个盒子为LUUU，前面n-4个盒子只要不含有连续三个U即可。共有2n-4-f(n-4)中方案
综上，f(n) = 2×f(n-1) + 2n-4-f(n-4)
1 #include <cstdio> 2 typedef long long LL; 3 4 LL f[35]; 5 6 int main() 7 { 8 int n; 9 f[3] = 1, f[4] = 3; 10 for(int i = 5; i <= 30; ++i) f[i] = 2*f[i-1] - f[i-4] + (1 << (i-4)); 11 while(scanf("%d", &n) == 1 && n) 12 printf("%lld ", f[n]); 13 14 return 0; 15 }