洛谷P3842 [TJOI2007] 线段
作者:
Air1222
,
2024-04-07 15:37:06
,
所有人可见
,
阅读 6
//蓝桥杯蜗牛原型
//到达一段,枚举到达的两个端点
//f[i][0]:走完当前线段且到达左端点
//f[i][1]:走完当前线段且到达右端点
//状态转移:枚举从上一个线段左/右端点到达当前线段的左/右端点的最小值
#include <iostream>
#include <cstring>
#include <cmath>
using namespace std;
const int N = 2e4+10;
typedef pair<int,int>PII;
#define x first
#define y second
int f[N][2];
PII a[N];
int main()
{
memset(f,0x3f,sizeof f);
int n;
cin>>n;
for(int i=1;i<=n;i++) cin>>a[i].x>>a[i].y;
f[1][0]=a[1].y+a[1].y-a[1].x-1;
f[1][1]=a[1].y-1;
for(int i=2;i<=n;i++)
{
f[i][0]=min(f[i-1][0]+abs(a[i-1].x-a[i].y),f[i-1][1]+abs(a[i-1].y-a[i].y))+a[i].y-a[i].x+1;
f[i][1]=min(f[i-1][0]+abs(a[i-1].x-a[i].x),f[i-1][1]+abs(a[i-1].y-a[i].x))+a[i].y-a[i].x+1;
}
cout<<min(f[n][0]+n-a[n].x,f[n][1]+n-a[n].y);
return 0;
}