[ACM] POJ1661 解题报告

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;
}

Leave a Reply

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