AC大美..之前一直WA到死 把search部分做成函数就AC了 实在不知道哪错了回头再看..
动态规划能不用递归就不用 循环从底层开始算到Jimmy落脚点那一层
1 | #include <cstdio> |
2 | #include <cstdlib> |
3 | typedef struct flat { |
4 | int l,r,h,lmin,rmin; |
5 | } Flat; |
6 | Flat a[1001]; |
7 | int N,MAX; |
8 |
9 | void search(int i,int k,bool bLeft); |
10 | int compare(const void *a,const void *b); |
11 |
12 | int main() { |
13 | int i,j,location; |
14 | int t,X,Y; |
15 | scanf("%d",&t); |
16 | while(t--) { |
17 | scanf("%d%d%d%d",&N,&X,&Y,&MAX); |
18 | for(i=1;i<=N;i++) |
19 | scanf("%d%d%d",&a[i].l,&a[i].r,&a[i].h); |
20 | qsort(a+1,N,sizeof(a[0]),compare); |
21 | for(i=1;i<=N+1;i++) { |
22 | if(a[i].l<=X&&a[i].r>=X||i==N+1) { |
23 | a[i-1].l=a[i-1].r=X; |
24 | a[i-1].h=Y; |
25 | location=i-1; |
26 | break; |
27 | } |
28 | } |
29 | for(i=N;i>=location;i--) { |
30 | for(j=i+1;j<=N;j++) |
31 | if(a[j].h!=a[i].h) |
32 | break; |
33 | search(i,j,true); |
34 | search(i,j,false); |
35 | } |
36 | printf("%d\n",a[location].lmin); |
37 | } |
38 | return 0; |
39 | } |
40 |
41 | void search(int i,int k,bool bLeft) { |
42 | int x,*min,gotol,gotor,fall; |
43 | if(bLeft) { |
44 | x=a[i].l; |
45 | min=&a[i].lmin; |
46 | } |
47 | else { |
48 | x=a[i].r; |
49 | min=&a[i].rmin; |
50 | } |
51 | for(;k<=N;k++) |
52 | if(a[k].l<=x&&a[k].r>=x) |
53 | break; |
54 |
55 | if(k==N+1) |
56 | if(a[i].h>MAX) |
57 | *min=-1; |
58 | else |
59 | *min=a[i].h; |
60 | else { |
61 | fall=a[i].h-a[k].h; |
62 | if(fall>MAX) |
63 | *min=-1; |
64 | else { |
65 | gotol=fall+x-a[k].l+a[k].lmin; |
66 | gotor=fall+a[k].r-x+a[k].rmin; |
67 | if(a[k].lmin==-1) |
68 | if(a[k].rmin==-1) |
69 | *min=-1; |
70 | else |
71 | *min=gotor; |
72 | else |
73 | if(a[k].rmin==-1) |
74 | *min=gotol; |
75 | else |
76 | if(gotol<gotor) |
77 | *min=gotol; |
78 | else |
79 | *min=gotor; |
80 | } |
81 | } |
82 | } |
83 |
84 | int compare(const void *a,const void *b) { |
85 | return ((Flat *)b)->h-((Flat *)a)->h; |
86 | } |
