AC大美..之前一直WA到死 把search部分做成函数就AC了 实在不知道哪错了回头再看..
动态规划能不用递归就不用 循环从底层开始算到Jimmy落脚点那一层
#include <cstdio> #include <cstdlib> typedef struct flat { int l,r,h,lmin,rmin; } Flat; Flat a[1001]; int N,MAX; void search(int i,int k,bool bLeft); int compare(const void *a,const void *b); int main() { int i,j,location; int t,X,Y; scanf("%d",&t); while(t--) { scanf("%d%d%d%d",&N,&X,&Y,&MAX); for(i=1;i<=N;i++) scanf("%d%d%d",&a[i].l,&a[i].r,&a[i].h); qsort(a+1,N,sizeof(a[0]),compare); for(i=1;i<=N+1;i++) { if(a[i].l<=X&&a[i].r>=X||i==N+1) { a[i-1].l=a[i-1].r=X; a[i-1].h=Y; location=i-1; break; } } for(i=N;i>=location;i--) { for(j=i+1;j<=N;j++) if(a[j].h!=a[i].h) break; search(i,j,true); search(i,j,false); } printf("%d\n",a[location].lmin); } return 0; } void search(int i,int k,bool bLeft) { int x,*min,gotol,gotor,fall; if(bLeft) { x=a[i].l; min=&a[i].lmin; } else { x=a[i].r; min=&a[i].rmin; } for(;k<=N;k++) if(a[k].l<=x&&a[k].r>=x) break; if(k==N+1) if(a[i].h>MAX) *min=-1; else *min=a[i].h; else { fall=a[i].h-a[k].h; if(fall>MAX) *min=-1; else { gotol=fall+x-a[k].l+a[k].lmin; gotor=fall+a[k].r-x+a[k].rmin; if(a[k].lmin==-1) if(a[k].rmin==-1) *min=-1; else *min=gotor; else if(a[k].rmin==-1) *min=gotol; else if(gotol<gotor) *min=gotol; else *min=gotor; } } } int compare(const void *a,const void *b) { return ((Flat *)b)->h-((Flat *)a)->h; }