bzoj 2321 数学

时间:2021-11-11 09:23:56

  首先我们假设两个点(i,j),(i,k)向中间移动一格,且k>j+1,那么我们可以获得的价值为k-j,这样,我们定义每个点的每个星的能量为a[(i,j)]=i*i+j*j,这样这两个点开始的能量为i*i+j*j+i*i+k*k,移动之后,两个点变为(i,j+1),(i,k-1),这时的能量为i*i+(j+1)*(j+1)+i*i+(k-1),这时的能量差为2*k-2*j,为获得价值的2倍,因为对于所有的价值获得都可以采用这样的方法,所以我们可以算出开始局面的能量和,结束局面的能量和,相减>>1就是答案。

  反思:显然没有发现这个优美的性质。

/**************************************************************
Problem: 2321
User: BLADEVIL
Language: C++
Result: Accepted
Time:56 ms
Memory:804 kb
****************************************************************/ //By BLADEVIL
#include <cstdio>
#define LL long long
using namespace std;
int n,m;
int main()
{
LL ans=,x;
scanf("%d%d",&n,&m);
for (int i=;i<=n;i++)
for (int j=;j<=m;j++)
scanf("%lld",&x),ans+=x*(i*i+j*j);
for (int i=;i<=n;i++)
for (int j=;j<=m;j++)
scanf("%lld",&x),ans-=x*(i*i+j*j);
printf("%lld\n",ans>>);
return ;
}