P7028: 序列重构
传统题
1.000s
时间限制
256MB
内存限制
0 提交
0 解决
【题目描述】
【题目描述】
Bessie
有一个数组 a1,…,aN
，其中 1≤N≤300
并对于所有 i 有 0≤ai≤10^9
。她不会告诉你数组 a
本身，但她会告诉你 a 的每个子数组的全距。也就是说，对于每对索引 i≤j，Bessie
告诉你 ri,j=max a[i…j]−min a[i…j]
。给定这些 r 的值，构造一个可以作为 Bessie 的原始数组的数组。你的数组中的数值应在[−10^9,10
^9]
范围内。
【
输入格式】
（从终端 /
标准输入读入）：
输入的第一行包含 N
。
以下 N
行，第 i 行包含整数 ri,i,ri,i+1,…,ri,N。
输入保证存在某个数组 a
，其中的数值在 [0,10
^9]
范围内，满足对于所有的 i≤j，有 ri,j=max a[i…j]−min a[i…j]
。
【
输出格式】
（输出至终端 /
标准输出）：
输出一行，包含 N
个整数 b1,b2,…,bN，在[−10
^9,10
^9]
范围内，表示你的数组。这些数需要满足对于所有的 i≤j 有 ri,j=max a[i…j]−min a[i…j]
。
【
输入样例】
：
3
0 2 2
0 1
0
【
输出样例】
：
1 3 2
【样例说明】
例如，r1,3=max a[1…3]−min a[1…3]=3−1=2
。
【
输入样例】
：
3
0 1 1
0 0
0
【
输出样例】
：
0 1 1
【样例说明】
这个样例满足子任务 1
的限制。
【
输入样例】
：
4
0 1 2 2
0 1 1
0 1
0
【
输出样例】
：
1 2 3 2
【样例说明】
这个样例满足子任务 2
的限制。
【
输入样例】
：
4
0 1 1 2
0 0 2
0 2
0
【
输出样例】
：
1 2 2 0
【
测试点性质】
：
测试点 5
满足 r1,N≤1。
测试点 6-8
满足对于所有1≤i<N 均有 ri,i+1=1。
测试点 9-14
没有额外限制。