abc429f题解

线段树大法好！

思路

首先有一个显然的结论，那就是最优路线一定不会往回走。

对于不修改的情况，考虑 dp。设

f_{i,j}

表示从

(1,1)

到

(j,i)

的最短路径。此时有转移方程

f_{i,j}=f_{i-1,k}+|k-j|

。

现在带上修改操作，考虑将 dp 放到线段树上进行维护，对于一段区间

[l,r]

我们设

f_{x,y}

表示从

(x,l)

到

(y,r)

的最短路径，合并时转移方程即为

f_{x,y}=fl_{x,k}+fr_{k,y}+1

。

最后考虑初始化。显然对于一列中

x

到达

y

时如果中间没有障碍物，代价即为

|x-y|

，有就设为

+\infty

即可。

Code

#include<bits/stdc++.h>
using namespace std;
const int N=200005;
const int INF=1e9;
char w[N][3];
struct node{
	int dp[3][3];
	void init(int x){
		for(int i=0;i<3;i++)
		for(int j=0;j<3;j++){
			dp[i][j]=abs(i-j);
			for(int k=min(i,j);k<=max(i,j);k++)if(w[x][k]=='#')dp[i][j]=INF;
		}
	}
};
node operator +(node a,node b){
	node ans;
	for(int i=0;i<3;i++)
	for(int j=0;j<3;j++){
		ans.dp[i][j]=INF;
		for(int k=0;k<3;k++)
			ans.dp[i][j]=min(ans.dp[i][j],a.dp[i][k]+b.dp[k][j]+1);
	}
	return ans;
}
struct segtree{
	node sum[N<<2];
	void pushup(int p){
		sum[p]=sum[p*2]+sum[p*2+1];
	}
	void build(int p,int l,int r){
		if(l==r){
			sum[p].init(l);
			return ;
		}
		int mid=(l+r)>>1;
		build(p*2,l,mid);
		build(p*2+1,mid+1,r);
		pushup(p);
	}
	void add(int p,int l,int r,int x,int v){
		if(l==r){
			if(w[l][v]=='#')w[l][v]='.';
			else w[l][v]='#';
			sum[p].init(l);
			return ;
		}
		int mid=(l+r)>>1;
		if(mid>=x)add(p*2,l,mid,x,v);
		else add(p*2+1,mid+1,r,x,v);
		pushup(p);
	}
	int query(){
		return sum[1].dp[0][2];
	}
}st;
int main(){
	int n;
	cin>>n;
	for(int i=0;i<3;i++)
	for(int j=1;j<=n;j++)cin>>w[j][i];
	st.build(1,1,n);
	int q;
	cin>>q;
	while(q--){
		int x,y;
		cin>>x>>y;
		st.add(1,1,n,y,x-1);
		if(st.query()>=INF)cout<<"-1\n";
		else cout<<st.query()<<"\n";
	}
}

文章操作

思路

Code

相关推荐

评论

abc429f题解