记忆化搜索,72分,求助!
查看原帖
记忆化搜索,72分,求助!
1031191
Zhang_Wenfu楼主2024/6/28 10:20
#include<bits/stdc++.h>
using namespace std;
int n,ans=1000000000;
map < pair<int,int>,int > f;

struct line{
	int l,r;
}l[20005];

template <class T> void read(T &k){
	char c;int t=1;
	while (!isdigit(c)){
		if (c == '-') t=-1;
		c=getchar();
	}
	while (isdigit(c)){
		k=k*10+c-48;
		c=getchar();
	}
	k *= t;
}

int dfs(int x,int y,int ind,int step){
	//cout << x << " " << y << " " << step << endl; 
	if (f[make_pair(x,y)]) return f[make_pair(x,y)];
	if (x == n+1){
		ans=min(ans,step-1+abs(n-y));
		return ans;
	}
	else if (y <= l[ind].l) return f[make_pair(x,y)]=dfs(x+1,l[ind].r,ind+1,step+1+l[ind].r-y);
	else if (y >= l[ind].r) return f[make_pair(x,y)]=dfs(x+1,l[ind].l,ind+1,step+1+y-l[ind].l);
	else return f[make_pair(x,y)]=min(dfs(x+1,l[ind].l,ind+1,step+l[ind].r-y+l[ind].r-l[ind].l+1),dfs(x+1,l[ind].r,ind+1,step+y-l[ind].l+l[ind].r-l[ind].l+1)); 
}

int main(){
	read(n);
	for (int i = 1;i <= n;i++){read(l[i].l);read(l[i].r);}
	dfs(1,1,1,0);
	cout << ans;
	return 0;
}
2024/6/28 10:20
加载中...