首页 > 代码库 > HDU 3485 Count 101

HDU 3485 Count 101

2024-07-27 13:13:30   220人阅读

Count 101

Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 65536/32768 K (Java/Others)
Total Submission(s): 1114    Accepted Submission(s): 568


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,00110100,0110,0111,10001001,1100,1110,1111
 

 

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

 

Recommend
zhengfeng
 
这个有点类似于数位DP，但是不是数位DP
设dp[i][j][k]表示长度为i串的最后两位数为i,j的不包含101的个数。
所以dp方程就有了：

dp[i][0][0]+=dp[i-1][0][1]+dp[i-1][0][0]
dp[i][0][1]+=dp[i-1][1][0]+dp[i-1][1][1]
dp[i][1][0]+=dp[i-1][0][0]
dp[i][1][1]+=dp[i-1][1][0]+dp[i-1][1][1]

最后取ans求总数就行了

#include<cstdio>#include<iostream>#include<cstring>#include<cmath>#include<stdlib.h>#include<algorithm>using namespace std;const int mod=9997;const int MAXN=10000+5;int dp[MAXN][2][2],n,ans[MAXN];void init(){    memset(dp,0,sizeof(dp));    memset(ans,0,sizeof(ans));    ans[0]=0;ans[1]=2;ans[2]=4;    dp[2][0][0]=dp[2][0][1]=dp[2][1][0]=dp[2][1][1]=1;    dp[1][1][0]=dp[1][0][0]=1;    for(int i=3;i<MAXN;i++)    {        dp[i][0][0]=(dp[i][0][0]+(dp[i-1][0][1]+dp[i-1][0][0])%mod)%mod;        dp[i][0][1]=(dp[i][0][1]+(dp[i-1][1][0]+dp[i-1][1][1])%mod)%mod;        dp[i][1][0]=(dp[i][1][0]+(dp[i-1][0][0])%mod)%mod;        dp[i][1][1]=(dp[i][1][1]+(dp[i-1][1][0]+dp[i-1][1][1])%mod)%mod;        ans[i]=(dp[i][0][0]+dp[i][0][1]+dp[i][1][0]+dp[i][1][1])%mod;    }}int main(){    init();    while(scanf("%d",&n)&&n!=-1)    {        printf("%d\n",ans[n]);    }    return 0;}
View Code

 

HDU 3485 Count 101


联系
我们