BZOJ 1295 最长距离

发表于 | 更新于

神思路啊！！

Link

Solution

最大值最大？？根本没有思路。 x+y=cx+y=c,x2+y2=c2−2xyx^2+y^2=c^2-2xy？走扁矩形的对角线求曼哈顿距离的最长路再转换？？ 换个思路，变成枚举。O(n2)O(n^2)地枚举所有点对，看它们的距离能否成为答案。 如何判断能否成为答案？？ 最短路求出最少经过多少障碍点与TT比较即可。因为偷懒用了Shortest Path Faster Algorithm，所以复杂度为O(nke)O(nke)(nn为点数)，其中k∈(2,n)k\in(2,n)。

Tips

暴力出奇迹。 用给出的题目的性质找不到答案，就寻找答案的性质(单峰->三分/单调->二分/总量不大->枚举所有可能性)，然后变成判定问题。

Code

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
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
//Code by Lucida
#include<bits/stdc++.h>
#define get(x) scanf("%d",&x)
//#define debug(x) std::cout<<#x<<'='<<x<<std::endl
template <class T> inline bool chkmx(T &a,const T &b){return a<b?a=b,1:0;}
template <class T> inline bool chkmn(T &a,const T &b){return a>b?a=b,1:0;}
using std::pair;
using std::queue;
const int MAXN=30+5,d[][2]={{0,1},{0,-1},{1,0},{-1,0}};
template<class T> inline T sqr(T x){return x*x;}
int map[MAXN][MAXN],sp[MAXN][MAXN][MAXN][MAXN],n,m;
void BFS(int x,int y,int sp[MAXN][MAXN])
{
	typedef pair<int,int> Node;
	static int inq[MAXN][MAXN],ut;
	static queue<Node> Q;
	sp[x][y]=map[x][y];Q.push(Node(x,y));inq[x][y]=++ut;
	while(!Q.empty())
	{
		x=Q.front().first,y=Q.front().second;inq[x][y]--;Q.pop();
		for(int p=0;p<4;++p)
		{
			int dx=x+d[p][0],dy=y+d[p][1];
			if(1<=dx && dx<=n && 1<=dy && dy<=m 
			   && chkmn(sp[dx][dy],sp[x][y]+map[dx][dy]) && inq[dx][dy]!=ut)
				Q.push(Node(dx,dy)),inq[dx][dy]=ut;
		}
	}
}
int main()
{
	freopen("input","r",stdin);
	memset(sp,31,sizeof(sp));
	int T,c;get(n),get(m),get(T);
	for(int i=1;i<=n;i++)
		for(int j=1;j<=m;j++)
		{
			while(!isdigit(c=getchar()));
			map[i][j]=c-'0';
		}
	for(int i=1;i<=n;i++)
		for(int j=1;j<=m;j++)
			BFS(i,j,sp[i][j]);
	double ANS=0;
	for(int x1=1;x1<=n;x1++)
		for(int y1=1;y1<=m;y1++)
			for(int x2=1;x2<=n;x2++)
				for(int y2=1;y2<=m;y2++)
					if(sp[x1][y1][x2][y2]<=T)
						chkmx(ANS,sqrt(sqr(x1-x2)+sqr(y1-y2)));
	printf("%.6lf\n",ANS);
	return 0;
}
/* AC Record(Bugs) *
 * 
 * * * * * * * * * */