社区讨论

72,wa3 wa4求助

P3842[TJOI2007] 线段参与者 2已保存回复 3

讨论操作

快速查看讨论及其快照的属性,并进行相关操作。

当前回复
3 条
当前快照
1 份
快照标识符
@lo8pl44a
此快照首次捕获于
2023/10/27 22:28
2 年前
此快照最后确认于
2023/10/27 22:28
2 年前
查看原帖
CPP
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<string>
#include<vector>
#include<queue>
const int maxn=2e4+5;
using namespace std;

long long n,l[maxn],r[maxn];
long long f[2][maxn];

int main(){
	scanf("%lld",&n);
	for(int i=1;i<=n;i++)
		scanf("%lld%lld",&l[i],&r[i]);
	f[0][1]=abs(l[1]-1)+r[1]-l[1];
	f[1][1]=abs(r[1]-1);
	for(int i=2;i<=n;i++){
		f[0][i]=min(f[0][i-1]+abs(l[i-1]-r[i]),f[1][i-1]+abs(r[i-1]-r[i]))+r[i]-l[i]+1;
		f[1][i]=min(f[0][i-1]+abs(l[i-1]-l[i]),f[1][i-1]+abs(r[i-1]-l[i]))+r[i]-l[i]+1;
	}
	printf("%lld",min(f[0][n]+n-l[n],f[1][n]+n-r[n]));
	return 0;
}

回复

3 条回复,欢迎继续交流。

正在加载回复...