題意：有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; }

?

?

《新程序員》：云原生和全面數字化實踐50位技術專家共同創作，文字、視頻、音頻交互閱讀

總結

以上是生活随笔為你收集整理的SPOJ 130 - Rent your airplane and make money（dp+优化）的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。