2825 codevs危险的组合(递推)

2825 危险的组合

时间限制: 1 s

空间限制: 64000 KB

题目等级 : 钻石 Diamond

题目描述 Description

有一些装有铀(用U表示)和铅(用L表示)的盒子，数量均足够多。要求把N个盒子放成一行，但至少有3个U放在一起，有多少种方法？

输入描述 Input Description

包含一个整数N

输出描述 Output Description

输出一个整数表示方法数。

样例输入 Sample Input

样例1：4

样例2：5

样例输出 Sample Output

样例1：3

样例2：8

数据范围及提示 Data Size & Hint

对于100%的数据（3<=N<=30）

样例1解释：

UUUL、LUUU、UUUU

样例2解释：

UUUUL、UUUUU、UUULU、UUULL、LUUUU、LUUUL、ULUUU、LLUUU

【思路】

当加入第n个的时候有两种情况（1 ）前面的n-1个已经满足了，而第n个要么是u要么是l，所以这这情况有 2*num（n-1）种

当加入第n个的时候，前面的n-1种没有满足情况，所以n-1个前面几个排列一定是 uul。。。所以在前面加入一个u正好满足要求就是UUUl...（第一个u是新加的）

而后面n-4个一共的情况（包括三个u没有挨在一起的）pow（2，n-4）种情况，再减去num（n-4）（也就是减去n-4个排列满足三个u在一起的情况，因为我们现在是找n-1个不满足的情况）。

就推出递推式了做出来了爽QWQ

【代码】

 #include<iostream>

 #include<cstdio>

 #include<cstdlib>

 #include<cmath>

 using namespace std;

 int n;

 int num(int x)

 {

     if(x<)return ;

     if(x==)return ;

     if(x==)return ;

     return *num(x-)+pow(,x-)-num(x-);

 }

 int main()

 {

     scanf("%d",&n);

     printf("%d",num(n));

     return ;

 }