链接：
https://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=521
题意：
有一些装有铀（用U表示）和铅（用L表示）的盒子，数量均足够多。
要求把n（n≤30）个盒子放成一行，但至少有3个U放在一起，有多少种放法？
例如，n=4, 5时答案分别为3, 8。
分析：
设答案为f(n)。既然有3个U放在一起，可以根据“最左边的3个U”的位置分类。假定是i、i+1和i+2这3个盒子，
则前i-1个盒子不能有3个U放在一起的情况。设n个盒子“没有3个U放在一起”的方案数为g(n)=2^n-f(n)，
则前i-1个盒子的方案有g(i-1)种。后面的n-i-2个盒子可以随便选择，有2^(n-i-2)种。
但是，即使前i-1个盒子内部不出现3个U，仍然可能和i、i+1和i+2组成3个U。
所以强制让第i-1个盒子（如果存在）放L，则前i-2个盒子内部不能出现连续的3个U。
因此f(n)=2^(n-3) + sum( g(i-2) * 2^(n-i-2) ), 2≤i≤n-2。
边界是f(0)=f(1)=f(2)=0。g(0)=1，g(1)=2，g(2)=4。注意上式中的2^(n-3)对应于i=1的情况。
代码：
import java.io.*;
import java.util.*; public class Main {
static final int UP = 30 + 5;
static int f[] = new int[UP], g[] = new int[UP]; static void constant() {
f[0] = 0; f[1] = 0; f[2] = 0; f[3] = 1;
g[0] = 1; g[1] = 2; g[2] = 4; g[3] = 7;
for(int n = 4; n <= 30; n++) {
f[n] = 1 << (n-3);
for(int i = 2; i <= n-2; i++) f[n] += g[i-2] * (1 << (n-i-2));
g[n] = (1 << n) - f[n];
}
} public static void main(String args[]) {
Scanner cin = new Scanner(new BufferedInputStream(System.in));
constant(); while(true) {
int n = cin.nextInt();
if(n == 0) break;
System.out.println(f[n]);
}
cin.close();
}
}