自动搬运

查看原文

来自洛谷，原作者为

	Mikefeng **

搬运于2025-08-24 22:43:34，当前版本为作者最后更新于2022-12-25 12:28:21，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

[USACO22DEC] Range Reconstruction S

题目描述

Bessie 有一个数组 $a_1, \cdots, a_N$，其中 $1 \le N \le 300$ 并对于所有 $i$ 有 $0 \le a_i \le 10^9$。她不会告诉你数组 $a$ 本身，但她会告诉你 $a$ 的每个子数组的全距。也就是说，对于每对索引 $i \le j$，Bessie 告诉你 $r_{i,j}= \max a[i \cdots j]-\min a[i \cdots j]$。给定这些 $r$ 的值，构造一个可以作为 Bessie 的原始数组的数组。你的数组中的数值应在 $[−10^9,10^9]$ 范围内。

做法

我们发现最有用的 $r$ 是 $r_{i,i+1}$，因为它可以告诉我们相邻两个数的差，于是就已经得到了 $2^n$ 的暴力解法。

暴力显然过不去，然而我们又发现一条性质，如果我们知道相邻三个数的极差，又知道了相邻两个数的差，我们是可以断定三个数之间的相对关系的，因为假设两个数的差分别是 $a,b$，那么三个数的极差一定是 $a+b$ 或 $|a-b|$。

所以我们先假定前两个数是第一个数更大，这样可以依次推出后面的数应该是几。

交了一发WA了。。。

这时发现如果前两个数相同，我们不能知道第三个数，因为不管第三个数更大还是更小三个数的极差都一样，所以我们推广一下做法，找到相邻的三组不一样的数，这样仍然能利用三组数的极差和相邻两组数分别的差算出答案。

代码

代码实现非常简洁。

const ll N=305;
const ll inf=1e18;
ll n,lst,minn=inf;
ll ans[N];
ll a[N][N];
int main(){
	n=read();
	F(i,1,n) F(j,i,n) a[i][j]=read();
	ans[1]=0;ans[2]=ans[1]+a[1][2];
	lst=2;
	F(i,3,n){
		if(a[lst-1][i]==a[lst-1][lst]+a[lst][i]){
			if(ans[lst]<ans[lst-1]) ans[i]=ans[lst]-a[lst][i];
			else ans[i]=ans[lst]+a[lst][i];
		}else{
			if(ans[lst]<ans[lst-1]) ans[i]=ans[lst]+a[lst][i];
			else ans[i]=ans[lst]-a[lst][i];
		}
		if(a[i-1][i]!=0) lst=i;
	}
	F(i,1,n) minn=min(minn,ans[i]);
	F(i,1,n) ans[i]-=minn;
	F(i,1,n){
		printf("%lld",ans[i]);
		if(i!=n) putchar(' ');
	}
	printf("\n");
	return 0;
}