题目：
题意倒是很好懂，就是你必须经过每一行的一些线段，求从起点到终点并且经过题目要求的线段的最短路
思路：
比较典型的DP，首先先想，每一层的最优肯定是由上一层限制的左端点或者右端点下来得到的，那么就可以有状态转移方程了
f[i][0]表示走完第i行且停在第i行的左端点最少用的步数
f[i][1]同理，停在右端点的最少步数。
那么转移就很简单了，走完当前行且停到左端点，那么一定是从右端点过来的，那么从上一行左端点转移的话就是
f[i][0]=abs(上一行左端点的坐标-本行右端点的坐标+本行线段长度)
思路倒是想的很快，但是一开始没想清楚方程，就分类讨论，然后写的又臭又长，但其实只需要几行代码就能解决的事
int main(){ #ifndef ONLINE_JUDGE freopen("P3842_1.in","r",stdin); freopen("P3842_1.out","w",stdout); #endif scanf("%d",&n); for(int i=1;i<=n;++i){ scanf("%d%d",a[i],a[i]+1); } dp[1][0]=a[1][1]+a[1][1]-a[1][0]-1; dp[1][1]=a[1][1]-1; for(int i=2;i<=n;++i){ dp[i][0]=mi(dp[i-1][0]+absi(a[i-1][0]-a[i][1])+a[i][1]-a[i][0]+1,dp[i-1][1]+absi(a[i-1][1]-a[i][1])+a[i][1]-a[i][0]+1); dp[i][1]=mi(dp[i-1][0]+absi(a[i-1][0]-a[i][0])+a[i][1]-a[i][0]+1,dp[i-1][1]+absi(a[i-1][1]-a[i][0])+a[i][1]-a[i][0]+1); } printf("%d\n",mi(dp[n][0]+n-a[n][0],dp[n][1]+n-a[n][1])); return 0; }
而我写的。。。。
一言难尽
#include<bits/stdc++.h> using namespace std; const int maxn=2e4+1000; int l[maxn],r[maxn],dp[maxn][2]; int dist(int l,int r ) { return abs(l-r); } int main() { int n,i,j,t; cin>>n; for(i=0;i<n;i++) { cin>>l[i]>>r[i]; } dp[0][1]=dist(1,r[0]); dp[0][0]=dist(1,r[0])+dist(l[0],r[0]); for(i=1;i<n;i++) { for(j=0;j<=1;j++) { int d1,d2; if(j==0) { int x=l[i-1],y=r[i-1]; if(l[i-1]>=l[i]&&l[i-1]<=r[i]) d1=(2*dist(r[i],l[i-1])+dist(l[i-1],l[i])); else if(l[i-1]>r[i]) d1=dist(l[i],r[i])+dist(r[i],l[i-1]); else d1=dist(l[i],r[i])*2+dist(l[i-1],l[i]); l[i-1]=r[i-1]; d2=d1; if(l[i-1]>=l[i]&&l[i-1]<=r[i]) d1=(2*dist(r[i],l[i-1])+dist(l[i-1],l[i])); else if(l[i-1]>r[i]) d1=dist(l[i],r[i])+dist(r[i],l[i-1]); else d1=dist(l[i],r[i])*2+dist(l[i-1],l[i]); l[i-1]=x; r[i-1]=y; if(d2+dp[i-1][0]<d1+dp[i-1][1]) dp[i][j]=dp[i-1][0]+d2; else dp[i][j]=dp[i-1][1]+d1; } else { int x=l[i-1],y=r[i-1]; if(l[i-1]>=l[i]&&l[i-1]<=r[i]) d1=(2*dist(l[i],l[i-1])+dist(l[i-1],r[i])); else if(l[i-1]<r[i]) d1=dist(l[i],r[i])+dist(l[i],l[i-1]); else d1=dist(l[i],r[i])*2+dist(l[i-1],r[i]); l[i-1]=r[i-1]; d2=d1; if(l[i-1]>=l[i]&&l[i-1]<=r[i]) d1=(2*dist(l[i],l[i-1])+dist(l[i-1],r[i])); else if(l[i-1]<r[i]) d1=dist(l[i],r[i])+dist(l[i],l[i-1]); else d1=dist(l[i],r[i])*2+dist(l[i-1],r[i]); if(d2+dp[i-1][0]<d1+dp[i-1][1]) dp[i][j]=dp[i-1][0]+d2; else dp[i][j]=dp[i-1][1]+d1; l[i-1]=x; r[i-1]=y; } } } if(dp[n-1][0]+(n-l[n-1])>(n-r[n-1]+dp[n-1][1])) cout<<(n-r[n-1]+dp[n-1][1])+n-1<<endl; else cout<<dp[n-1][0]+(n-l[n-1])+n-1<<endl; return 0; }
