2014
04-04

# Count 101

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?

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.

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.

3
4
-1

7
12
HintWe 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


#include <stdio.h>
int main()
{
int dp[10001]={0,2,4,7};
for(int i=4;i<10000;i++)
dp[i] = (2*dp[i-1]-dp[i-2]+dp[i-3])%9997;
int n;
while(scanf("%d",&n),n+1)
printf("%d\n",dp[n]);
return 0;
}


1. 在方法1里面：

//遍历所有的边，计算入度
for(int i=0; i<V; i++)
{
degree = 0;