HDOJ 题目3485 Count 101（递推）

Count 101

Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 65536/32768 K (Java/Others)

Total Submission(s): 1118    Accepted Submission(s): 572

Problem Description You know YaoYao is fond of his chains. He has a lot of chains and each chain has n diamonds on it. There are two kinds of diamonds, labeled 0 and 1. We can write down the label of diamonds on a chain. So each chain can be written as a sequence consisting of 0 and 1.

We know that chains are different with each other. And their length is exactly n. And what’s more, each chain sequence doesn’t contain “101” as a substring. 

Could you tell how many chains will YaoYao have at most?

Input There will be multiple test cases in a test data. For each test case, there is only one number n(n<10000). The end of the input is indicated by a -1, which should not be processed as a case.  

Output For each test case, only one line with a number indicating the total number of chains YaoYao can have at most of length n. The answer should be print after module 9997.  

Sample Input

3
4
-1
        

Sample Output

7
12

   
    
     Hint
    We can see when the length equals to 4. We can have those chains:
0000,0001,0010,0011
0100,0110,0111,1000
1001,1100,1110,1111

   
    
        

Source 2010 ACM-ICPC Multi-University Training Contest（5）——Host by BJTU  

Recommend zhengfeng   |   We have carefully selected several similar problems for you:   3484  3478  3479  3480  3481    ac代码

#include<string.h>
#include<stdio.h>
#define mod 9997
int a[10010]={0,2,4,7,12};
void fun()
{
	int i;
	for(i=5;i<10010;i++)
	{
		a[i]=(a[i-1]+a[i-2]+a[i-4])%mod;
	}
}
int main()
{
	int n;
	fun();
	while(scanf("%d",&n)!=EOF,n!=-1)
	{
		printf("%d\n",a[n]);
	}
}