0x59 单调队列优化DP-白红宇

0x59 单调队列优化DP

阅读量：4570 次

发布时间：2019-06-08

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

倍增DP太难啦心情好再回去做

poj1821 先让工匠按s排序，f[i][j]表示枚举到第i个工匠涂了j个木板（注意第j个木板不一定要涂）

那么f[i][j]可以直接继承f[i-1][j]和f[i][j-1]

此外 f[i][j]=max(j-l[i]+1<=k<=s[i]){f[i-1][k-1]+(j-k+1)*p}

按照单调队列运用的思想，维护f[i-1][k-1]-k*p的最大值

#include
      
       #include
       
        #include
        
         #include
         
          #include
          
           #include
           
            using namespace std;struct node{ int l,p,s;}a[110];bool cmp(node n1,node n2){ return n1.s
            
             =f[i-1][q[t]-1]-a[i].p*q[t])t--; q[++t]=k; } for(int j=1;j
             
              q[h])h++; f[i][j]=max(f[i-1][j],f[i][j-1]); if(h<=t)f[i][j]=max(f[i][j],a[i].p*(j+1)+f[i-1][q[h]-1]-a[i].p*q[h]); } } printf("%d\n",f[n][m]); return 0;}

poj1821

poj3017 神题（其实还好吧）

设f[i]表示1~i的最小值，f[i]=min(∑(k=j+1~i)a[k]<=m){f[j]+max(j+1~i)(a[k])}

然而，可以证明的是，可能成为最优决策的j，一定是j+1~i的最大值，或者是满足∑(k=j+1~i)a[k]<=m最小的j

那么就可以维护一个a[j]递减的单调队列，但是f[j]+max(j+1~i)(a[k])是不单调的，要用set把值记录

#include
      
       #include
       
        #include
        
         #include
         
          #include
          
           #include
           
            #include
            
             using namespace std;typedef long long LL;int a[110000],q[110000];LL f[110000];multiset
             
              s;int main(){ int n;LL m; scanf("%d%lld",&n,&m); for(int i=1;i<=n;i++) { scanf("%d",&a[i]); if(a[i]>m){printf("-1\n");return 0;} } int tp=1;LL sum=0; int h=1,t=0; for(int i=1;i<=n;i++) { sum+=a[i];while(sum>m)sum-=a[tp++]; while(h<=t&&a[i]>=a[q[t]]) { if(h
              
               q[h]) { if(h

poj3017

hdu2191 （纯粹是给单调队列维护多重背包找个例题）

把一个数拆成u+p*V的形式，f[u+p*V]=max(p-C<=k<=p-1){f[u+k*V]+(p-k)*W}

维护下f[u+k*V]-k*W

#include
      
       #include
       
        #include
        
         #include
         
          #include
          
           #include
           
            using namespace std;int f[110],q[110];int main(){ int T; scanf("%d",&T); while(T--) { int m,n,W,V,C; scanf("%d%d",&m,&n); memset(f,0,sizeof(f)); for(int i=1;i<=n;i++) { scanf("%d%d%d",&V,&W,&C); for(int u=0;u
            
             =0;p--) { while(h<=t&&q[h]>p-1)h++; if(h<=t)f[u+p*V]=max(f[u+p*V],f[u+q[h]*V]+(p-q[h])*W); if(p-C-1>=0) { while(h<=t&&(f[u+q[t]*V]-q[t]*W)<=(f[u+(p-C-1)*V]-(p-C-1)*W))t--; q[++t]=p-C-1; } } } } int ans=0; for(int i=1;i<=m;i++)ans=max(ans,f[i]); printf("%d\n",ans); } return 0;}