[总结] 单调队列优化 DP

· · 个人记录

Fence

F[i,j]=P_i* j+max_{j-L_i\leq k\leq S_i-1} \ \{F[i-1,k]+P_i* k\} 
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
const int maxn = 16010,maxm = 110;
struct node{
    int L,P,S;
}a[110];
bool operator <(const node a,const node b){
    return a.S<b.S;
}
int n,m;
int f[maxm][maxn],q[maxn];
int calc(int i,int k){
    return f[i-1][k]-a[i].P*k;
}
int main(){
    scanf("%d%d",&n,&m);
    for(int i=1;i<=m;i++)scanf("%d%d%d",&a[i].L,&a[i].P,&a[i].S);
    sort(a+1,a+1+m);
    /////正解
    for(int i=1;i<=m;i++){
        int head=1,tail=0;
        for(int k=max(0,a[i].S-a[i].L);k<=a[i].S-1;k++){
            while(head<=tail && calc(i,q[tail])<=calc(i,k))tail--;
            q[++tail]=k;
        }
        for(int j=1;j<=n;j++){//状态 
            f[i][j]=max(f[i-1][j],f[i][j-1]);
            ////
            if(j>=a[i].S){
                while(head<=tail && q[head]<j-a[i].L)head++;
                if(head<=tail)f[i][j]=max(f[i][j],calc(i,q[head])+a[i].P*j);
            }
        }
    }
    printf("%d",f[m][n]);
    return 0;
}

注意初始化单调队列

多重背包（单调队列优化）

基本思想：对于每一个物品，按照余数分组（这才可以转移）

F[u+p* V_i]= max\{F[u+k* V_i]+(p-k)* W_i\}

等价于

F[u+p*V_i]=max\{F[u+k*V_i]-k*W_i \}+p*W_i\ \ (k\in[p-C_i,p-1])

这也体现了单调队列优化 DP 的基本思想：把状态和决策两部分分开来，维护k 这个决策集合

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
const int maxn = 1e5 + 10 , maxm = 2e4 + 100;
int f[maxm],v[maxn],w[maxn],C[maxn],q[maxn];//体积，价值，个数，单调队列 
int n,M;
int calc(int i,int u,int k){
    return f[u+k*v[i]]-k*w[i];
}
int main(){
    scanf("%d%d",&n,&M);
    memset(f,0xcf,sizeof f);
    f[0]=0;
    for(int i=1;i<=n;i++){
        scanf("%d%d%d",&v[i],&w[i],&C[i]);
        for(int u=0;u<v[i];u++){
            int head=1,tail=0;
            int maxp=(M-u)/v[i];//对于当前余数最多能装几个
            for(int k=maxp-1;k>=max(0,maxp-C[i]);k--){
                while(head<=tail && calc(i,u,q[tail])<=calc(i,u,k))tail--;
                q[++tail]=k;
            }
            for(int p=maxp;p>=0;p--){
                while(head<=tail && q[head]>p-1)head++;
                if(head<=tail){//转移 
                    f[u+p*v[i]]=max(f[u+p*v[i]],calc(i,u,q[head])+p*w[i]);
                }
                if(p-C[i]-1>=0){//加入新决策 
                    while(head<=tail && calc(i,u,q[tail])<=calc(i,u,p-C[i]-1))tail--;
                    q[++tail]=p-C[i]-1;
                }
            }
        }
    }
    int ans=-1;
    for(int i=1;i<=M;i++)ans=max(ans,f[i]);
    printf("%d",ans);
    return 0;
}

P2569 [SCOI2010]股票交易

分四种情况讨论即可，借这道题强调几个细节。

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
const int maxn = 2010;
#define LL long long
int n,maxp,W,from;
LL AP[maxn],BP[maxn],AS[maxn],BS[maxn];
LL f[maxn][maxn];
int q[maxn];
int head=1,tail=0;
LL calc1(int i,int k){return f[from][k]+k*AP[i];}
LL calc2(int i,int k){return f[from][k]+k*BP[i];}
int main(){
    //freopen("trade7.in","r",stdin);
    scanf("%d%d%d",&n,&maxp,&W);
    memset(f,0xcf,sizeof f);
    for(int i=0;i<=n;i++)f[i][0]=0;
    for(int i=1;i<=n;i++)scanf("%lld%lld%lld%lld",AP+i,BP+i,AS+i,BS+i);
    for(int i=1;i<=n;i++){
        head=1;tail=0;
        for(int j=0;j<=maxp;j++)f[i][j]=max(f[i][j],f[i-1][j]);
        from=max(0,i-W-1);
        //买入
        head=1;tail=0;
        for(int j=0;j<=maxp;j++){
            while(head<=tail && q[head]<j-AS[i])head++;
            while(head<=tail && calc1(i,q[tail])<=calc1(i,j))tail--;
            q[++tail]=j;
            if(head<=tail)f[i][j]=max(f[i][j],calc1(i,q[head])-j*AP[i]);
        }
        //卖出
        head=1;tail=0;
        for(int j=maxp;j>=0;j--){ 
            while(head<=tail && q[head]>j+BS[i])head++;
            while(head<=tail && calc2(i,q[tail])<=calc2(i,j))tail--;
            q[++tail]=j;
            if(head<=tail)f[i][j]=max(f[i][j],calc2(i,q[head])-j*BP[i]);
        }
    }
    //for(int i=1;i<=n;i++)for(int j=0;j<=maxp;j++)printf("f[%d][%d]: %lld\n",i,j,f[i][j]);
    LL ans=-1e19;
    for(int i=0;i<=maxp;i++)ans=max(ans,f[n][i]);
    printf("%lld\n",ans);
    return 0;
}

细节