UVA 1546 - Complete the sequence!(差分法)
1119 ワード
UVA 1546 - Complete the sequence!
タイトルリンク
題意:多項式の前のs項を与えて、後のc項を求めて、できるだけ小さいことを要求します
考え方:差分法を利用して、元のシーケンスに対してs-1回の差分を求めて、法則を発見することができて、それから多くの項目に対して、逆に押し返せばいいです
コード:
タイトルリンク
題意:多項式の前のs項を与えて、後のc項を求めて、できるだけ小さいことを要求します
考え方:差分法を利用して、元のシーケンスに対してs-1回の差分を求めて、法則を発見することができて、それから多くの項目に対して、逆に押し返せばいいです
コード:
#include <stdio.h>
#include <string.h>
const int N = 205;
int t, s, c, a[N][N];
int main() {
scanf("%d", &t);
while (t--) {
scanf("%d%d", &s, &c);
memset(a, 0, sizeof(a));
for (int i = 0; i < s; i++)
scanf("%d", &a[0][i]);
for (int i = 1; i < s; i++)
for (int j = 0; j < s - i; j++)
a[i][j] = a[i - 1][j + 1] - a[i - 1][j];
for (int i = 0; i < c; i++) {
for (int j = s - 1; j >= 0; j--)
a[j][s - j + i] = a[j + 1][s - j - 1 + i] + a[j][s - j - 1 + i];
printf("%d%c", a[0][s + i], (i == c - 1 ? '
' : ' '));
}
}
return 0;
}