首页 > ACM题库 > HDU-杭电 > HDU 3485-Count 101-动态规划-[解题报告]HOJ
2014
04-04

HDU 3485-Count 101-动态规划-[解题报告]HOJ

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

题目链接:Click here~~

题意:

一种只有0、1两种元素的串,问长度为 i 的串中包含多少个不含有“101”的串。

解题思路:

令 dp[i] 表示长度为 i 的串满足要求的串的个数。

很容易想到 dp[i] = 2*dp[i-1] – { dp[i-1] 中末尾两位是"10"的串的个数 }。

而 { } 中的内容又可以表示成 dp[i-1] 中末位是“0”的串的个数 – dp[i-2] 中末位是“0”的串的个数。

又因为 dp[j] 中末位是“0”的个数等于 dp[j-1] 。

于是得到状态转移方程:dp[i] = 2*dp[i-1] – (dp[i-2] – dp[i-3])。

#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;
}

参考:http://blog.csdn.net/dgq8211/article/details/8005113


  1. 在方法1里面:

    //遍历所有的边,计算入度
    for(int i=0; i<V; i++)
    {
    degree = 0;
    for (j = adj .begin(); j != adj .end(); ++j)
    {
    degree[*j]++;
    }
    }

    为什么每遍历一条链表,要首先将每个链表头的顶点的入度置为0呢?
    比如顶点5,若在顶点1、2、3、4的链表中出现过顶点5,那么要增加顶点5的入度,但是在遍历顶点5的链表时,又将顶点5的入度置为0了,那之前的从顶点1234到顶点5的边不是都没了吗?

  2. Excellent Web-site! I required to ask if I might webpages and use a component of the net web website and use a number of factors for just about any faculty process. Please notify me through email regardless of whether that would be excellent. Many thanks

  3. Thanks for using the time to examine this, I truly feel strongly about it and enjoy finding out far more on this subject matter. If achievable, as you achieve knowledge