2171: An Easy Problem!
Status | In/Out | TIME Limit | MEMORY Limit | Submit Times | Solved Users | JUDGE TYPE |
---|---|---|---|---|---|---|
stdin/stdout | 3s | 8192K | 627 | 186 | Standard |
It's an easy problem!
N-bit sequences is a string of digitals which contains only '0' and '1'. You should determine the number of n-bit sequences that contain no three continuous 1's. For example, for n = 3 the answer is 7 (sequences 000, 001, 010, 011, 100, 101, 110 are acceptable while 111 is not).
Input
For each line, you are given a single positive integer N no more than 40 on a line by itself.
Output
Print a single line containing the number of n-bit sequences which have no three continuous 1's.
Sample Input
1 2 3
Sample Output
2 4 7
动态规划。所有的串都能按照最末两位分成四组。假设在n位合法的0、1串中,以00结尾的串的个数为f0(n),以01结尾的串个数为f1(n),以10结尾的串个数为f2(n),以11结尾的串个数为f3(n),则n位合法的0、1串的总数f(n)=f0(n)+f1(n)+f2(n)+f3(n)。当串的长度扩展到n+1位时,我们看这它们各自的个数如何动态变化。从n位到n+1位,只需要在n位串的末尾追加一位0或一位1即可。对四个函数分类讨论:
以00结尾:加0后变成以00结尾,加1后变成01结尾;
以01结尾:加0后变成以10结尾,加1后变成11结尾;
以10结尾:加0后变成以00结尾,加1后变成01结尾;
以11结尾:加0后变成以10结尾,加1后不合法。
所以,有: f0(n+1) = f0(n) + f2(n), f1(n+1) = f0(n) + f2(n), f2(n+1) = f1(n) + f3(n), f3(n+1) = f1(n)。
当n为2时,有f0(2) = f1(2) = f2(2) = f3(2) = 1。这样,经过递推可以很快计算出结果。中间要考虑溢出的情况。当n = 37时,结果超过了70亿,必须用double类型。
整理得到 a[i]=a[i-1]+a[i-2]+a[i-3];
#include<stdio.h>
int main()
{
double a[50]={0,2,4,7};
for( int i=4;i<=40;i++)
{
a[i]=a[i-1]+a[i-2]+a[i-3];
}
int n;
while(scanf("%d",&n)==1)
{
printf("%.0lf/n",a[n]);
}
return 0;
}