首页 > 代码库 > HDOJ 1121 Complete the Sequence

HDOJ 1121 Complete the Sequence

2024-07-06 11:36:28   223人阅读

【题目大意】
有一个数列P，它的第i项是当x=i时，一个关于x的整式的值。
给出数列的前S项，你需要输出它的第S+1项到第S+C项，并且使整式的次数最低。
多测。

【数据范围】
数据组数≤5000，S+C≤100

 

思路：使用差分的方法进行解题，然后再逆向回去

 

实例：
　　原数列1，2，4，7，11，16，22，29……
　　第一次相减：1，2，3，4，5，6，7……
　　第二次相减：1，1，1，1，1，1……
　　所有元素都相同了
　　所以下一项就是1+7+29=37，再下一项是1+8+37=46

 

 1 #include<stdio.h>
 2 #define NN 102
 3 int main()
 4 {
 5     int T, i, j, S, C;
 6     int f[NN][NN];
 7     scanf("%d", &T);
 8     while (T--){
 9         scanf("%d%d", &S, &C);
10         for (i = 0; i < S; i++)
11             scanf("%d", &f[0][i]);
12         for (i = 1; i < S; i++)
13             for (j = 0; i + j < S; j++)
14                 f[i][j] = f[i - 1][j + 1] - f[i - 1][j];
15         for (i = 1; i <= C; i++)
16             f[S - 1][i] = f[S - 1][0];
17         for (i = S - 2; i >= 0; i--)
18             for (j = S - i; j < C + S; j++)
19                 f[i][j] = f[i][j - 1] + f[i + 1][j - 1];
20         for (i = S; i < S + C - 1; i++)
21             printf("%d ", f[0][i]);
22         printf("%d\n", f[0][i]);
23     }
24     return 0;
25 }

 


联系
我们