SPOJ130_Rent your airplane and make money_单调队列DP实现-白红宇

SPOJ130_Rent your airplane and make money_单调队列DP实现

阅读量：5352 次

发布时间：2019-06-15

本文共 1617 字，大约阅读时间需要 5 分钟。

题意比较简单，状态转移方程也比较容易得出：

f[i]=max{ f [ j ] }+p[i]，（j的结束时间在i开始时间之前）

若i开始之前没有结束的j，则f[i]=p[i];

因数据量太大（n<=10000）因此必须优化，这里使用单调队列降低时间复杂度

首先按开始时间排序，队列里存的是编号，队列要求是开始时间严格递增，f[i]利润值严格递增，每次只需维护单调队列，就能将dp部分降到O(n)，因插入队列是用到二分查找，所以总的时间为O(nlogn)

维护单调队列的思路：求f[i]时，从队头开始遍历，找到在i开始时间之前最后结束的j，然后将j之前的全部出队，插入时，首先根据i的结束时间二分查找出i可能插入的位置x，然后看该位置之后的f[x]小于等于f[i]的编号x全部删除，然后若i可以放在此处（两种情况：1.空队时，2.f[i]比f[x]小比f[x-1]大时，刚开始这个地方没处理好，WA了n次！！！），则将i插入单调队列。最后求出最大的f[i]即可。

/*************************************************************************    > File Name: A.cpp    > Author: Chierush    > Mail: qinxiaojie1@gmail.com     > Created Time: 2013年07月26日 星期五 10时52分21秒 ************************************************************************/#include 
     
      #include 
      
       #include 
       
        #include 
        
         #include 
         
          #include 
          
           #include 
           
            #include 
            #include 
             
              #include 
              
               #define LL long long#define LLU unsigned long longusing namespace std;struct node{ int s,t,p; bool operator<(const node &c) const { if (s!=c.s) return s

q;int f[10005];int find(int x){ if (a[q[q.size()-1]].s+a[q[q.size()-1]].t

=x) r=m; else return m; } else return m; } }}int main(){ int T,n; scanf("%d",&T); while (T--) { scanf("%d",&n); for (int i=0;i

1 && a[q[1]].s+a[q[1]].t<=a[i].s) q.erase(q.begin()); if (a[q[0]].s+a[q[0]].t<=a[i].s) f[i]=a[i].p+f[q[0]]; else f[i]=a[i].p; int x=find(a[i].s+a[i].t); while (q.size()>x && f[i]>=f[q[x]]) q.erase(q.begin()+x); if (!q.size() || (q.size()==x && f[i]>f[q[x-1]]) || (q.size()>x && a[q[x]].s+a[q[x]].t>a[i].s+a[i].t && (!x || f[q[x-1]]

转载于:https://www.cnblogs.com/Chierush/p/3219404.html

你可能感兴趣的文章