【递推】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];}