[ACM] POJ1661 解题报告

84 Replies

AC大美..之前一直WA到死 把search部分做成函数就AC了 实在不知道哪错了回头再看..
动态规划能不用递归就不用 循环从底层开始算到Jimmy落脚点那一层

[c]
#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;
}
[/c]

84 thoughts on “[ACM] POJ1661 解题报告”

Leave a Reply

Your email address will not be published. Required fields are marked *