1363: Count 101 （经典数位dp）
1363: Count 101
Time Limit: 1 Sec Memory Limit: 128 Mb Submitted: 393 Solved: 154
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
不能出现101，问你这样序列的个数
数位dp
可以由很多dp方式，比如三维dp
做过一个非常类似的题
dp1[i]:表示长度为i的满足要求的（不出现101）的以0结尾的方案数
dp2[i]:表示长度为i的满足要求的（不出现101）的以1结尾的方案数目
dp3[i]:表示长度为i的满足要求的以(1或者0)结尾的方案数目
dp1：
想一下dp1[i]的含义（以0结尾）
因为题目要求是没有101
所以对dp1，第i位置
前面的第i-1位置可以是0，可以是1
所以：dp1[i]=dp1[i-1]+dp2[i-1]
想一下dp2[i]的含义（以1结尾）
题目要求没有101
对dp2的第i位置
所以肯定第i位置肯定是1（dp2的含义）
所以前面的第i-1个位置也只能是1
前面的第i-2个位置也只能是0
这样才不会有101出现
所以：
dp2[i]=dp2[i-1]+dp1[i-2]
#include<stdio.h> #include<iostream> #include<math.h> #include<algorithm> #include<memory.h> #include<memory> using namespace std; #define max_v 10005 #define mod 9997 int dp1[max_v]; int dp2[max_v]; int dp3[max_v]; int main() { dp1[1]=1; dp1[2]=2; dp2[1]=1; dp2[2]=2; dp3[1]=dp1[1]+dp2[1]; dp3[2]=dp1[2]+dp2[2]; for(int i=3;i<10000;i++) { dp1[i]=(dp1[i-1]+dp2[i-1])%mod; dp2[i]=(dp1[i-2]+dp2[i-1])%mod; dp3[i]=(dp1[i]+dp2[i])%mod; } int n; while(~scanf("%d",&n)) { if(n<0) break; printf("%d\n",dp3[n]); } return 0; } /* 给你长度为n的序列，只能由0或者1组成 不能出现101，问你这样序列的个数 分析： 数位dp 可以由很多dp方式，比如三维dp 做过一个非常类似的题 dp1[i]:表示长度为i的满足要求的（不出现101）的以0结尾的方案数 dp2[i]:表示长度为i的满足要求的（不出现101）的以1结尾的方案数目 dp3[i]:表示长度为i的满足要求的以(1或者0)结尾的方案数目 dp3[i]=dp1[i]+dp2[i]; 所以我们只需要得的dp1和dp2的转移方程 dp1： 想一下dp1[i]的含义（以0结尾） 因为题目要求是没有101 所以对dp1，第i位置 前面的第i-1位置可以是0，可以是1 所以：dp1[i]=dp1[i-1]+dp2[i-1] dp2： 想一下dp2[i]的含义（以1结尾） 题目要求没有101 对dp2的第i位置 所以肯定第i位置肯定是1（dp2的含义） 所以前面的第i-1个位置也只能是1 前面的第i-2个位置也只能是0 这样才不会有101出现 所以： dp2[i]=dp2[i-1]+dp1[i-2] 所以通过dp1和dp2，我们就可以知道dp3了 注意：记得dp的初始化 其实还可以用斐波那契写，听学弟说的.... */