SPOJ 130 - Rent your airplane and make money（dp+优化）

题意：有n列预定航班，从st时刻开始出发，飞行时间为d，花费为p，且同一时刻不能有两个航班，求最大的花费

对航班的开始时间（或结束时间）按升序排序，从后往前找到对应结束时间所在的航班位置（如按结束时间排序则需要从前往后找到开始时间所在航班位置，需要使用二分法）

d[i]=max(d[j]+p)

#include <stdio.h>

#include <string.h>

#include <math.h>

#include <algorithm>

using namespace std;

typedef struct

{

    int s;

    int e;

    int d;

    int p;

}pl;

pl a[10005];

int d[10005];

int find(int x,int L,int n)

{

    int l=L+1,r=n-1,mid=(l+r)/2;

    while(l<r)

    {

        if(x>a[mid].s)l=mid+1;

        else r=mid;

        mid=(l+r)/2;

    }

    return a[mid].s>=x ? mid : mid+1;

}

int cmp(pl a,pl b)

{

    return a.s<b.s;

}

int main()

{

    int T,n;

    scanf("%d",&T);

    while(T--)

    {

        scanf("%d",&n);

        for(int i=0;i<n;i++)

        {

            scanf("%d%d%d",&a[i].s,&a[i].d,&a[i].p);

            a[i].e=a[i].s+a[i].d;

        }

        sort(a,a+n,cmp);

        memset(d,0,sizeof(d));

        for(int i=n-1;i>=0;i--)

        {

            d[i]=d[i+1];

            int L=find(a[i].e,i,n);

            if(d[L]+a[i].p>d[i])

                d[i]=d[L]+a[i].p;

        }

        printf("%d\n",d[0]);

    }

    return 0;

}

巴特西

SPOJ 130 - Rent your airplane and make money（dp+优化）

最新文章

热门文章