看着复杂，其实理一理之后还好
重要的是
伪代码技巧
#include<cstdio> #include<cstdlib> #include<algorithm> #include<cstring> using namespace std; int n,mxh; const int N=1e3+3,inf=1<<30; struct node { int l,r,h; bool operator < (const node & o) const { return h>o.h; } //我先处理上面的，然后递归深入 }d[N]; int f[N][2]; int find(int st,int x ,int low) { for(int i=st;i<=n;i++) if(d[i].h <low)//超过mxh，就算找到了也没用，不如直接清掉 return n+1; else if(d[i].l <=x && d[i].r >=x )//恰好落在平台边缘，视作落在平台上 return i; return n+1; } bool vis[N]; void work(int nw) { //我已经memset成inf了，所以直接找能走的更新就行 if(vis[nw]) return ; vis[nw]=true; //往左走 int x=d[nw].l ; int nx=find(nw+1 ,x ,d[nw].h -mxh ); if(nx<=n) { work(nx); f[nw][0]=min( f[nx][0]+x-d[nx].l ,f[nx][1]+d[nx].r -x) + d[nw].h -d[nx].h ; } else if(d[nw].h <=mxh) f[nw][0]=d[nw].h ; //往右走 x=d[nw].r ; nx=find(nw+1 ,x ,d[nw].h -mxh ); if(nx<=n) { work(nx); f[nw][1]=min( f[nx][0]+x-d[nx].l ,f[nx][1]+d[nx].r -x) + d[nw].h -d[nx].h ; } else if(d[nw].h <=mxh) f[nw][1]=d[nw].h ; } int main() { while(~scanf("%d%d%d%d",&n,&d[0].l ,&d[0].h ,&mxh)) { memset(f,0x7f,sizeof(f)); for(int i=1;i<=n;i++) scanf("%d%d%d",&d[i].l ,&d[i].r ,&d[i].h ); d[0].r =d[0].l ; sort(d+1,d+n+1); work(0); printf("%d ",min(f[0][0],f[0][1])); } return 0; }
#include<cstdio> #include<cstdlib> #include<algorithm> #include<cstring> using namespace std; int n,mxh; const int N=1e3+3,inf=1<<30; struct node { int l,r,h; bool operator < (const node & o) const { return h>o.h; } //我先处理上面的，然后递归深入 }d[N]; int f[N][2]; int find(int st,int x ,int low) { for(int i=st;i<=n;i++) if(d[i].h <low)//超过mxh，就算找到了也没用，不如直接清掉 return n+1; else if(d[i].l <=x && d[i].r >=x )//恰好落在平台边缘，视作落在平台上 return i; return n+1; } bool vis[N]; void work(int nw) { //我已经memset成inf了，所以直接找能走的更新就行 if(vis[nw]) return ; vis[nw]=true; //往左走 int x=d[nw].l ; int nx=find(nw+1 ,x ,d[nw].h -mxh ); if(nx<=n) { work(nx); f[nw][0]=min( f[nx][0]+x-d[nx].l ,f[nx][1]+d[nx].r -x) + d[nw].h -d[nx].h ; } else if(d[nw].h <=mxh) f[nw][0]=d[nw].h ; //往右走 x=d[nw].r ; nx=find(nw+1 ,x ,d[nw].h -mxh ); if(nx<=n) { work(nx); f[nw][1]=min( f[nx][0]+x-d[nx].l ,f[nx][1]+d[nx].r -x) + d[nw].h -d[nx].h ; } else if(d[nw].h <=mxh) f[nw][1]=d[nw].h ; } int main() { while(~scanf("%d%d%d%d",&n,&d[0].l ,&d[0].h ,&mxh)) { memset(f,0x7f,sizeof(f)); for(int i=1;i<=n;i++) scanf("%d%d%d",&d[i].l ,&d[i].r ,&d[i].h ); d[0].r =d[0].l ; sort(d+1,d+n+1); work(0); printf("%d ",min(f[0][0],f[0][1])); } return 0; }