MnZn求条,悬3关
查看原帖
MnZn求条,悬3关
529038
Butterfly__qwq楼主2024/6/5 13:38
#include<bits/stdc++.h>
using namespace std;
const int N=100005,L=17;
int n,q,d[N][2][2],dis[N][L][2][2],dp[2][2],id[N][2];
int solve(int d1,int g1,int d2,int g2)
{
	for(int j:{0,1})for(int k:{0,1})dp[j][k]=0;
	dp[0][g1^1]=abs(d[d1][0][0]-d[d1][1][0])+abs(d[d1][0][1]-d[d1][1][1]);
	for(int i=L-1;i>=0;i--)
	{
		if(d2-d1<(1<<i))continue;
		for(int j:{0,1})dp[1][j]=min(dp[0][0]+dis[d1][i][0][j],dp[0][1]+dis[d1][i][1][j]);
		for(int j:{0,1})dp[0][j]=dp[1][j];
		d1+=(1<<i);
	}
	return dp[0][g2];
}
int main()
{
	ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
	cin>>n;
	for(int i=1;i<n;i++)for(int j:{0,1})for(int k:{0,1})cin>>d[i][j][k];
	for(int i=1;i<n;i++)for(int j:{0,1})for(int k:{0,1})dis[i][0][j][k]=abs(d[i][j][0]+1-j-d[i+1][k][0])+abs(d[i][j][1]+j-d[i+1][k][1])+1;
	for(int i=1;i<n;i++)for(int j=1;j<L;j++)if(i+(1<<j)<=n)for(int k:{0,1})for(int l:{0,1})dis[i][j][k][l]=min(dis[i][j-1][k][0]+dis[i+(1<<(j-1))][j-1][0][l],dis[i][j-1][k][1]+dis[i+(1<<(j-1))][j-1][1][l]);
	cin>>q;
	for(int i=1,x1,y1,x2,y2,d1,d2;i<=q;i++)
	{
		cin>>x1>>y1>>x2>>y2;
		d1=max(x1,y1);d2=max(x2,y2);
		if(d1>d2)
		{
			swap(d1,d2);
			swap(x1,x2);
			swap(y1,y2);
		}
		if(d1==d2)cout<<abs(x1-x2)+abs(y1-y2)<<'\n';
		else cout<<min(abs(x1-d[d1][0][0])+abs(y1-d[d1][0][1])+min(solve(d1,0,d2-1,0)+abs(x2-d[d2-1][0][0]-1)+abs(y2-d[d2-1][0][1])+1,solve(d1,0,d2-1,1)+abs(x2-d[d2-1][1][0])+abs(y2-d[d2-1][1][1]-1)+1),abs(x1-d[d1][1][0])+abs(y1-d[d1][1][1])+min(solve(d1,1,d2-1,0)+abs(x2-d[d2-1][0][0]-1)+abs(y2-d[d2-1][0][1])+1,solve(d1,1,d2-1,1)+abs(x2-d[d2-1][1][0])+abs(y2-d[d2-1][1][1]-1)+1))<<'\n';
	}
}

WA on 5

2024/6/5 13:38
加载中...