这题递推到了n-4项，值得记录。
问题描述：给n个取值为1或0的数，要求组成的序列中1必须连续，问能组成多少个这样的序列。
对前几项很容易写出来：
1：0
2：00 11
3：000 011 110 111
4：0000 0011 0110 1100 0111 1110 1111
f[1]=1;f[2]=2;f[3]=4;f[4]=7;求f[n].
对所有序列，最后一位要么是1要么是0.（这不是废话吗？真不是废话）
显然，对任意满足条件的序列，在后面加一个0，得到的序列必然满足要求。F[N]+=F[N-1];
这样结尾是0的数目算出来了。下面要算结尾是1 的序列总数目。
以1结尾至少是11，向前推两位 ，最后4位的所有可能情况：0011 0111 1111
在任意满足要求的序列后面添加11，得到的序列必然满足要求，F[N]+=F[N-2];
但是结果中只有0011 1111 序列，因为在F[N-2]中没有结尾是01的序列，这样结尾为1的序列总数就没有找全。
那么结尾为0111的序列总数就是在第N-4后面加上0111 F[N]+=F[N-4];
综上所述：F[N]=F[N-1]+F[N-2]+F[N-4];
HDU1297
#include <bits/stdc++.h> using namespace std; const int maxn=1001; const int MOD=1e8; int ka[maxn][maxn]; void init() { ka[1][0]=1; ka[2][0]=2; ka[3][0]=4; ka[4][0]=7; for(int i=5;i<maxn;i++) { for(int j=0;j<maxn;j++) { ka[i][j]=ka[i-1][j]+ka[i-2][j]+ka[i-4][j]; } for(int j=0;j<maxn-1;j++) { ka[i][j+1]+=ka[i][j]/MOD; ka[i][j]%=MOD; // cout<<ka[i][j]<<endl; } } } void out(int n) { int i; for(i=maxn-1;i>=0&&!ka[n][i];i--); printf("%d",ka[n][i]); for(i=i-1;i>=0;i--) printf("d",ka[n][i]); printf("\n"); } int main() { int n; init(); while(cin>>n) out(n); return 0; }
转载于:https://www.cnblogs.com/star-and-me/p/6910191.html
相关资源：数据结构—成绩单生成器