72分求助,注释全部写清楚的记忆化搜索
查看原帖
72分求助,注释全部写清楚的记忆化搜索
139334
拱垲楼主2023/11/19 10:12
#include <iostream>
#include <cstring>
#include <string>
#include <cstdio>
#include <cstdlib>
#include <algorithm>
#include <stack>
#include <queue>
#include <map>
#include <unordered_map>
#include <cmath>
#define int long long
using namespace std;

int dp[20000+2][3];
int n,L[20000+2],R[20000+2];
int dfs(int row,int col)//now col is left or right
{
	if(dp[row][col]!=-1)return dp[row][col];
	int ANS=1e16;

	if(col==1)//towards L[row]
	{
		//from L[row-1]
		if(L[row-1]<=R[row])
			ANS=min(ANS,dfs(row-1,1)+1+R[row]-L[row-1]+R[row]-L[row]);
		else 
			ANS=min(ANS,dfs(row-1,1)+1+L[row-1]-L[row]);
		//from R[row-1]
		if(R[row-1]<=R[row])
			ANS=min(ANS,dfs(row-1,2)+1+R[row]-R[row-1]+R[row]-L[row]);
		else 
			ANS=min(ANS,dfs(row-1,2)+1+R[row-1]-L[row]);
	}
	else//towards R[row]
	{
		//from L[row-1]
		if(L[row-1]<=L[row])
			ANS=min(ANS,dfs(row-1,1)+1+R[row]-L[row-1]);
		else 
			ANS=min(ANS,dfs(row-1,1)+1+L[row-1]-L[row]+R[row]-L[row]);
		//from R[row-1]
		if(R[row-1]<=L[row])
			ANS=min(ANS,dfs(row-1,2)+1+R[row]-R[row-1]);
		else 
			ANS=min(ANS,dfs(row-1,2)+1+R[row-1]-L[row]+R[row]-L[row]);
	}
	for(int i=L[row-1];i<=R[row-1]/2;i++)
	{
		
		if(i<=R[row]&&i>=L[row])
			ANS=min(ANS,dfs(row-1,2)+R[row-1]-i+1+2*(R[row]-max(i,col))+2*(min(i,col)-L[row])+max(i,col)-min(i,col));
		else if(i>R[row]) ANS=min(ANS,dfs(row-1,2)+1+i-L[row]+col-L[row]);
		else if(i<L[row]) ANS=min(ANS,dfs(row-1,2)+1+R[row]-i+R[row]-col);
	}
		
	return dp[row][col]=ANS;
}
signed main()
{
	scanf("%ld",&n);
	for(int i=1;i<=n;i++)
	{
		scanf("%ld%ld",&L[i],&R[i]);
		for(int j=0;j<3;j++)dp[i][j]=-1;//li~ri->0~ri-li
	}
	dp[1][1]=R[1]-1+R[1]-L[1];
	dp[1][2]=R[1]-1;
	cout<<min(n-R[n]+dfs(n,2),n-L[n]+dfs(n,1))<<endl;
	return 0;
}

2023/11/19 10:12
加载中...