数位DP。。。。

Count 101

3
4
-1

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
 

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>

using namespace std;

const int mod=9997;

int dp[11000][2][2],n;
int ans[11000];

void init()
{
    dp[1][1][0]=dp[1][0][0]=1;
    dp[2][0][0]=dp[2][1][0]=1;
    dp[2][0][1]=dp[2][1][1]=1;

    ans[0]=0;ans[1]=2;ans[2]=4;
    for(int i=3;i<11000;i++)
    {
        for(int j=0;j<2;j++)
        {
            for(int k=0;k<2;k++)
            {
                if(j==0)
                {
                    dp[i][j][k]+=(dp[i-1][k][0]+dp[i-1][k][1])%mod;
                }
                else if(j==1)
                {
                    if(k==1)
                    {
                         dp[i][j][k]+=(dp[i-1][k][0]+dp[i-1][k][1])%mod;
                    }
                    else
                    {
                        dp[i][j][k]+=dp[i-1][k][0];
                    }
                }
                dp[i][j][k]=dp[i][j][k]%mod;
            }
        }
        ans[i]=(dp[i][1][0]+dp[i][1][1]+dp[i][0][1]+dp[i][0][0])%mod;
    }

}

int main()
{
    init();
while(scanf("%d",&n)!=EOF&&~n)
{
    printf("%d\n",ans[n]);
}
    return 0;
}

HDOJ 3485 Count 101,布布扣,bubuko.com

HDOJ 3485 Count 101

原文：http://blog.csdn.net/u012797220/article/details/20959395