题目

这次，OI山成为了雷曼兔那无尽的冒险传说的新舞台！传说OI山中埋藏着巨大的宝藏，伴随着这个传说的是一个迷题：最瑰丽的舞者将达至精灵世界的彼岸……
经过仔细推敲，雷曼兔发现这是一个提示宝藏埋藏位置的谜语，在该谜语中指出了一个特定的路径，只有经过了该路径宝藏才会出现，具体情况如下：
OI山的地势图可以看作一个N*N的数字矩阵，由1-N^2的数字组成（每个数字出现且仅出现一次），这些数字表示每个地点的地势高低。雷曼兔的出发点在最高的山顶处，并且每次雷曼兔可以从其当前所在的位置跳跃到任何一个比当前地点高度低的位置，假设雷曼兔该次跳跃从坐标(x1,y1)跳到了坐标(x2,y2)，则这次跳跃的华丽度定义为v=(|x1-x2|+|y1-y2|)^2。而开启宝藏秘密的路径就是从山顶不断跳跃直到山底（高度最低点）的华丽度总和最高的路径，而现在我们想要知道的是这个最高的华丽度总和是多少

题解

对于每个高度$i$，枚举$i+1$至$n$的每一个高度，设$dp[i]$是从高度$n$跳到高度$i$的最大华丽度，则$dp_i=max\lbrace dp_i, dp_j+(|X_i-X_j|+|Y_i+Y_j|)^2\rbrace $,最后$dp_1$即为结果。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26

#include<cstdio>
#include<algorithm>
const int MAXN=50*50+5;
int n,pos[MAXN][2],x,a,dp[MAXN];
int abs(int x){return x>0?x:-x;}
int main()
{
	scanf("%d",&n);
	for(int i=1;i<=n;i++)
		for(int j=1;j<=n;j++)
		{
			scanf("%d",&a);
			x=std::max(x,a);
			pos[a][0]=i;pos[a][1]=j;
		}
	for(int i=x-1;i>=1;i--)
		for(int j=i+1;j<=x;j++)
		{
			a=abs(pos[i][0]-pos[j][0])+abs(pos[i][1]-pos[j][1]);
			a=a*a;
		//	printf("debug %d %d %d\n",i,j,a);
			dp[i]=std::max(dp[i],dp[j]+a);
		}
	printf("%d",dp[1]);
	return 0;
}