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

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

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

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

 
#include    
#include    
#include    
#include    
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(la[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=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 
#include 
#include 
#include 
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(la[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=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;
}