58ptsWA#3#4#5求调+玄关
查看原帖
58ptsWA#3#4#5求调+玄关
1035893
2789617221guo楼主2025/7/22 19:46

rt,我的思路和题解的代码一样,但是调了半天还是WA,求大犇调。

#include<bits/stdc++.h>

using namespace std;

const int INF=0x3f3f3f3f;
const double EPS=1e-8;
const int N=2e4+5;

struct line{
	long long l,r;
} a[N];

int n;
long long dp[N][2];

//dp[i][0]表示走到第i条线段的左端点的最小路程,dp[i][1]表示走到第i条线段的右端点的最小路程。
//dp[1][0]=dis(1,r1)+dis(r1,l1),dp[1][1]=dis(1,r1);
//dp[i][0]=min(dp[i-1][0]+dis(l[i-1],r[i])+dis(r[i],l[i]),dp[i-1][1]+dis(r[i-1],r[i])+dis(r[i],l[i]))+1
//dp[i][1]=min(dp[i-1][0]+dis(l[i-1],l[i])+dis(l[i],r[i]),dp[i-1][1]+dis(r[i-1],l[i])+dis(r[i],l[i]))+1

long long dis(int x,int y){
	return llabs(x-y);
}

int main(){
	ios::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr);
	cin>>n;
	for(int i=1;i<=n;i++) cin>>a[i].l>>a[i].r;
	dp[1][0]=dis(1,a[1].r),dp[1][1]=dis(1,a[1].r)+dis(a[1].r,a[1].l);
	for(int i=2;i<=n;i++){
		dp[i][0]=min(dp[i-1][0]+dis(a[i-1].l,a[i].r)+dis(a[i].r,a[i].l),dp[i-1][1]+dis(a[i-1].r,a[i].r)+dis(a[i].r,a[i].l))+1;
		dp[i][1]=min(dp[i-1][0]+dis(a[i-1].l,a[i].l)+dis(a[i].l,a[i].r),dp[i-1][1]+dis(a[i-1].r,a[i].l)+dis(a[i].l,a[i].r))+1;
	}
	cout<<min(dp[n][0]+dis(a[n].l,n),dp[n][1]+dis(a[n].r,n))<<endl;
	return 0;
}
2025/7/22 19:46
加载中...