[Luogu1848][USACO12OPEN]书架Bookshelf DP+set+决策单调性

题目链接：https://www.luogu.org/problem/show?pid=1848

题目要求书必须按顺序放，其实就是要求是连续的一段。于是就有DP方程$$f[i]=min\{f[j]+max\{h_k\}\}$$其中的k以及j的关系应该满足$$\sum_{k=j+1}^iw_k<=L$$

这样是$O(n^2)$的肯定不行。发现对于一个$h[i]$到前一个比它大的$h[j]$之间，都被$h[i]$所影响这，且这些影响某一段区间的关键点是单调下降的，同时发现$f[j]$总不会比$f[j+1]$更劣，证明显然。

于是我们只需要维护这样一个关键点集就可以从中取得最优答案。观察DP方程中的条件限制，发现前面的点可能会被从前往后舍去，而后面的点可以把之前的点给覆盖掉，想到用单调队列维护。

队首元素的删除用$w$的区间和来维护，队尾元素则直接用新加入的$h[i]$不断合并掉就好了。

然后对于每一个当前合法的关键点，我们都需要记录其对应的答案，每次取最小值。不仅需要插入，同时还需要从中删除掉不合法的答案。我们可以用双堆或者平衡树来做，当然set也是可以的。

 #include<cstdio>

 #include<cstring>

 #include<algorithm>

 #include<set>

 using namespace std;

 typedef long long ll;

 int inline readint(){

     int Num;char ch;

     while((ch=getchar())<''||ch>'');Num=ch-'';

     while((ch=getchar())>=''&&ch<='') Num=Num*+ch-'';

     return Num;

 }

 int n,m;

 int h[],w[],la;

 ll f[],sum;

 int q[],head,tail;

 bool in[];

 multiset <ll> s;

 //  f[i]=f[j]+max(h[k])  sigma(w[k])<=L  k:i->j+1

 int main(){

     n=readint();

     m=readint();

     la=head=q[]=;

     tail=sum=;

     in[]=true;

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

         h[i]=readint();

         w[i]=readint();

         sum+=w[i];

         while(sum>m){

             if(in[la]){

                 s.erase(f[la-]+h[la]);

                 in[la]=false;

                 head++;

             }

             else h[la]=h[la-];

             sum-=w[la++];

         }

         if(!in[la]){

             h[la]=h[la-];

             s.insert(f[la-]+h[la]);

             q[--head]=la;

             in[la]=true;

         }

         q[++tail]=i;

         s.insert(f[i-]+h[i]);

         in[i]=true;

         while(head<=tail&&h[q[tail]]<=h[i]){

             s.erase(f[q[tail]-]+h[q[tail]]);

             in[q[tail]]=false;

             tail--;

         }

         h[q[++tail]]=h[i];

         s.insert(f[q[tail]-]+h[q[tail]]);

         in[q[tail]]=true;

         f[i]=*s.begin();

     }

     printf("%lld\n",f[n]);

     return ;

 }

巴特西

[Luogu1848][USACO12OPEN]书架Bookshelf DP+set+决策单调性

最新文章

热门文章