自动搬运

查看原文

来自洛谷，原作者为

	linfourxu もうトサカに来たぜ

搬运于2025-08-24 21:31:11，当前版本为作者最后更新于2021-06-26 11:55:38，作者可能在搬运后再次修改，您可在原文处查看最新版

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

以下是正文

容易发现，答案只与初态末态有关且唯一，那么考虑设一个势能函数使得每移动一次，势能的减少量等于答案的增加量。值得注意的是，这种思想在“鞅的停时问题”中也非常常用。

考虑设 $f(x,y)$ 表示位于 $(x,y)$ 的一颗“星”的势能，容易发现势能是每颗星的势能的加和，且 $x$ 维度上的势能与 $y$ 维度上的势能相互独立且等价。这些也是“鞅的停时问题”中设势能函数相当常用也相当容易发现的结论。

那么就可以化简势能函数为 $f(x)$ 表示某一维上位于 $x$ 位置的一颗"星"的势能，根据变化不难列出 $f(x_1)+f(x_2)-f(x_1+1)-f(x_2-1)=x2-x1-1$ 其中 $x1<x2$，该式子含义即为”驱动“位于 $x_1$ 的一颗星与位于 $x_2$ 的一颗星。

简单移项可得 $f(x_1+1)-f(x_1)-(x_1+1)=f(x_2)-f(x_2-1)-x2$ 所以我们设的势能函数只需要满足 $f(x)-f(x-1)-x$ 为定值即可，不妨令这个定值与 $f(0)$ 都为 $0$，当然你令这两个值为多少都行。

那么不难得到 $f(x)$ 的通项为 $\frac{x^2+x}{2}$，当然这个通项与你 $f(0)$ 和定值的取值有关。

那么这题中每颗星总的势能即可表示为 $\frac{x^2+y^2+x+y}{2}$，答案即为初态的总势能减去末态的总势能。

rint n=read<int>(),m=read<int>();rll ans=0;
for(rint i=1;i<=n;i++)
	for(rint j=1;j<=m;j++)
		ans+=read<int>()*(i*(i+1)/2+j*(j+1)/2);
for(rint i=1;i<=n;i++)
	for(rint j=1;j<=m;j++)
		ans-=read<int>()*(i*(i+1)/2+j*(j+1)/2);
printf("%lld\n",ans);