题意

题目背景

Magic Land 上的时间又过了若干世纪„„

现在，人们谈论着一个传说：从前，他们的祖先来到了一个位于东方的岛屿，
那里简直就是另外一个世界。善于分析与构造的 Magic Land 上的人们总是不明
白那里的人们是如何不借助精确的实验与计算驱动和操纵魔法。

题目描述

偶然地，一个魔法使（Magician）来到了Magic Land，在临走的时候留下了
一个神奇的盒子，叫做星之器（Casket of star）。
虽然不知道这个盒子是做什么的，但是经过了大量的实验和计算后，人们已
经清楚它的一些事实：

1．星之器之中有N×M 个区域，可看作分成 N行和 M列的格子，每个区域之中有若干单位的称为“星”的对象，这个对象的最小单位已经被确定，所以，这个数量总是整数。

2．魔法使可以驱动星之器中位于同一行或同一列的不相邻（有公共边的区域称为相邻的）两个区域中各 1 单位的“星”，使得它们分别向中心移动 1 格。

3．每一次使用2 中的方法驱动“星”，将会产生魔力，魔法使会得到这一部分魔力。魔力的量等于这个两个区域之间所间隔的区域数。

这样，我们可以用一个 N×M 的数表来表示星之器的状态，比如 N=2，M=3
时：

2 0 1                                     1 2 0

5 1 4                                     5 1 4

当星之器为左图的状态时，通过操纵第一行的第 1 和3 个区域中的“星” （加粗的数字对应的区域），变为右图所示的状态，同时，将产生 1 单位的魔力（因
为这两个区域之间恰好隔了 1 个区域）。

在经过了进一步的研究之后，人们知道了这个星之器最初的状态（Ini）以及最终被他们得到时的状态（Fin）。

你希望知道，星之器最多帮助它的拥有者提供了多少的魔力。即：经过一系列上述操作由初态（Ini）变为终态（Fin），至多产生多少魔力。

需要注意的是，显然操作过程中每个区域内“星”的数量不能是负的，即：如果那个区域已经没有“星”了，当然就不能继续操作了。

输入输出格式

输入格式：

第一行包含两个正整数N、M 表示星之器的大小。

接下来的N 行，每行包含 M个自然数：Iniij，描绘了初态（Ini）。

在一个空行后的N 行，每行包含 M 个自然数：Fin ，描绘了终态（Fin）。

输出格式：

输出一个正整数，表示至多产生的魔力。

输入输出样例

输入样例#1：
复制

输出样例#1：
复制

说明

100%的数据中1 ≤ N，M ≤ 200，Iniij，Finij ≤ 1000。

所有数据保证了至少存在一个操作方法使得星之器由初态变为终态，同时保
证了初态与终态不是完全相同的。

分析

每次操作只会移动行或者列其中一个，两种情况并不相关，所以可以分开计算。

考虑以为情况，\(x,y(x<y)\)格子各向中间移动了一步，则贡献为

\[y-x-1 \\
=\frac{y^2-(y-1)^2+x^2-(x+1)^2}2
\]

所以可以定义一个点的势能为\(val[i,j]*\frac{i^2+j^2}2\)，那么初态减去终态的势能就是操作所释放出来的能量。

至于为什么是最大值呢？因为方案唯一，最大值就一幌子。

时间复杂度\(O(NM)\)

代码

#include<bits/stdc++.h>

#define rg register

#define il inline

#define co const

template<class T>il T read(){

    rg T data=0,w=1;rg char ch=getchar();

    while(!isdigit(ch)) {if(ch=='-') w=-1;ch=getchar();}

    while(isdigit(ch)) data=data*10+ch-'0',ch=getchar();

    return data*w;

}

template<class T>il T read(rg T&x) {return x=read<T>();}

typedef long long ll;

co int N=51;

int n,m;

ll ans;

int main(){

	read(n),read(m);

	for(int i=1;i<=n;++i)for(int j=1;j<=m;++j)

		ans+=read<int>()*(i*i+j*j);

	for(int i=1;i<=n;++i)for(int j=1;j<=m;++j)

		ans-=read<int>()*(i*i+j*j);

	printf("%lld\n",ans/2);

	return 0;

}

巴特西

LG1861 星之器

题意

题目背景

题目描述

输入输出格式

输入输出样例

说明

分析

代码

最新文章

热门文章