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

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

补充：软件开发 , C++ ,

上一个：命令行选项的处理
下一个：Zjnu Stadium(hdu3047带权并查集)