首页 > ACM题库 > HDU-杭电 > HDU 1121 Complete the Sequence-动态规划-[解题报告] C++
2013
11-27

HDU 1121 Complete the Sequence-动态规划-[解题报告] C++

Complete the Sequence

问题描述 :

You probably know those quizzes in Sunday magazines: given the sequence 1, 2, 3, 4, 5, what is the next number? Sometimes it is very easy to answer, sometimes it could be pretty hard. Because these "sequence problems" are very popular, ACM wants to implement them into the "Free Time" section of their new WAP portal.
ACM programmers have noticed that some of the quizzes can be solved by describing the sequence by polynomials. For example, the sequence 1, 2, 3, 4, 5 can be easily understood as a trivial polynomial. The next number is 6. But even more complex sequences, like 1, 2, 4, 7, 11, can be described by a polynomial. In this case, 1/2.n^2-1/2.n+1 can be used. Note that even if the members of the sequence are integers, polynomial coefficients may be any real numbers.

Polynomial is an expression in the following form:

P(n) = aD.n^D+aD-1.n^D-1+…+a1.n+a0

. If aD <> 0, the number D is called a degree of the polynomial. Note that constant function P(n) = C can be considered as polynomial of degree 0, and the zero function P(n) = 0 is usually defined to have degree -1.

输入:

There is a single positive integer T on the first line of input. It stands for the number of test cases to follow. Each test case consists of two lines. First line of each test case contains two integer numbers S and C separated by a single space, 1 <= S < 100, 1 <= C < 100, (S+C) <= 100. The first number, S, stands for the length of the given sequence, the second number, C is the amount of numbers you are to find to complete the sequence.

The second line of each test case contains S integer numbers X1, X2, … XS separated by a space. These numbers form the given sequence. The sequence can always be described by a polynomial P(n) such that for every i, Xi = P(i). Among these polynomials, we can find the polynomial Pmin with the lowest possible degree. This polynomial should be used for completing the sequence.

输出:

For every test case, your program must print a single line containing C integer numbers, separated by a space. These numbers are the values completing the sequence according to the polynomial of the lowest possible degree. In other words, you are to print values Pmin(S+1), Pmin(S+2), …. Pmin(S+C).

It is guaranteed that the results Pmin(S+i) will be non-negative and will fit into the standard integer type.

样例输入:

4
6 3
1 2 3 4 5 6
8 2
1 2 4 7 11 16 22 29
10 2
1 1 1 1 1 1 1 1 1 2
1 10
3

样例输出:

7 8 9
37 46
11 56
3 3 3 3 3 3 3 3 3 3

http://acm.hdu.edu.cn/showproblem.php?pid=1121

题目大意:给你一个整数序列包含S个整数,让你找到这个序列满足的多项式 P(n) = aD.n^D+aD-1.n^D-1+…+a1.n+a0,当这个多项式的阶最小时,输出接下来的满足这个多项式C个整数

算法分析:hdu推荐为dp题,没思路,找到解题报告(http://rchardx.is-programmer.com/posts/16142.html),说是差分。我的理解是这样的:对于每一项求其与前一项的差,然后观察找规律,对于任意满足多项式P(n) = aD.n^D+aD-1.n^D-1+…+a1.n+a0的D阶多项式,取一阶差分得:tmp = P(n) – (n – 1)肯定是个D-1阶多项式,以此类推,取n-1阶差分,就只剩下一个数d (程序中为f[n-1][0]), 如果d = 0,如果想使得P(n)的阶最小,第n-1阶差分中接下来的m个数应该都为0,如果d != 0,当接着的m个数都为d时,则第n-2阶为1阶多项式(只有一阶多项式(a1.n + a0, 公差为a1)的差分才为一个常数),第n-1阶为0阶多项式,才能保证阶D最小

 

#include<stdio.h>
#define NN 102
int main()
{
    int T, i, j, S, C;
    int f[NN][NN];
    scanf("%d", &T);
    while (T--){
        scanf("%d%d", &S, &C);
        for (i = 0; i < S; i++)
            scanf("%d", &f[0][i]);
        for (i = 1; i < S; i++)
            for (j = 0; i + j < S; j++)
                f[i][j] = f[i - 1][j + 1] - f[i - 1][j];
        for (i = 1; i <= C; i++)
            f[S - 1][i] = f[S - 1][0];
        for (i = S - 2; i >= 0; i--)
            for (j = S - i; j < C + S; j++)
                f[i][j] = f[i][j - 1] + f[i + 1][j - 1];
        for (i = S; i < S + C - 1; i++)
            printf("%d ", f[0][i]);
        printf("%d\n", f[0][i]);
    }
    return 0;
}

 

 

 


  1. for(int i=1; i<=m; i++){
    for(int j=1; j<=n; j++){
    dp = dp [j-1] + 1;
    if(s1.charAt(i-1) == s3.charAt(i+j-1))
    dp = dp[i-1] + 1;
    if(s2.charAt(j-1) == s3.charAt(i+j-1))
    dp = Math.max(dp [j - 1] + 1, dp );
    }
    }
    这里的代码似乎有点问题? dp(i)(j) = dp(i)(j-1) + 1;这个例子System.out.println(ils.isInterleave("aa","dbbca", "aadbbcb"));返回的应该是false

  2. 博主您好,这是一个内容十分优秀的博客,而且界面也非常漂亮。但是为什么博客的响应速度这么慢,虽然博客的主机在国外,但是我开启VPN还是经常响应很久,再者打开某些页面经常会出现数据库连接出错的提示

  3. 在方法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的边不是都没了吗?

  4. 学算法中的数据结构学到一定程度会乐此不疲的,比如其中的2-3树,类似的红黑树,我甚至可以自己写个逻辑文件系统结构来。