【递推】wikioi 2825 危险的组合

题目链接：http://wikioi.com/problem/2825/

分析：
本以为是DP，也有人用DP做，但是看到有人202B代码潇洒解决，还是试一试递推吧。。。

先列举出来前几项：

0 0 1 3 8 20 47 107 238 520 1121

好像没什么规律昂。。。

再列出2的幂，减一减。。。

0 0 1 3 8 20 47 107 238 520 1121
0 0 1 2 4 8 16 32 64 128 256 a[]
0 0 0 1 4 12 31 75 174 392 865 b[]

很明显，下面两行的和等于上面两行。

中间一行是2^(n-3)。

剩下最后一行了，再找。。。

0 0 0 1 2 4 7 13 24 44 81 c[]

这是后面的数减前面的数的二倍得到的结果。

有规律了吧？

从第七项开始，c[i]=c[i-1]+c[i-2]+c[i-3]，好像可做了。。。

b[i]=b[i-1]*2+c[i].

最后输出a[n]+b[n]即可。

代码：

#include<iostream>#include<cmath>using namespace std;int a[31]={0},b[31]={0},c[31]={0},n;int main(){a[3]=1;a[4]=2;a[5]=4;b[4]=1;b[5]=4;c[3]=1;c[4]=1;c[5]=2;for (int i=6;i<=n;i++) { a[i]=pow(2,i-3); c[i]=c[i-1]+c[i-2]+c[i-3]; b[i]=b[i-1]*2+c[i]; } cout<<a[n]+b[n];}