ZR 集训 Day10 – DP 优化

ooliver 发布于 13 小时前 122 次阅读 OI

AI 摘要

从单调队列到斜率优化，再到李超线段树和凸包上二分——Day10 的 DP 优化课直接把难度拉满。多重背包、玩具装箱、任务安排……原来暴力转移换个视角，就能被这些冷门但暴力的数据结构瞬间加速。如果你也受够了 TLE，今天的内容会让你重新认识 DP。

ZR 集训 Day10 - DP 优化

P1886 【模板】单调队列 / 滑动窗口

模板，不知道为啥之前一直 20 pts。

C++
#include<bits/stdc++.h>
using namespace std;

const int N=1e6+5;
int n,k;
int a[N],q[N];

void get(int y){
    int l=0,r=0;
    for(int i=1;i<=n;i++){
        while(l<=r&&a[q[r]]>=a[i]) r--;
        q[++r]=i;
        while(l<=r&&i-q[l]+1>k) l++;
        if(i>=k) cout<<y*a[q[l]]<<" ";
    }
}

signed main(){
    cin>>n>>k;
    for(int i=1;i<=n;i++) cin>>a[i];
    get(1);
    cout<<"\n";
    for(int i=1;i<=n;i++) a[i]=-a[i];
    get(-1);
    return 0;
}

P1776 宝物筛选

单调队列优化多重背包。

$$
\begin{aligned}
dp[i]&=\max{dp[i-kw]+kv} \\
dp[i]&=\max{dp[i-kw]-\frac{(i-kw)v}{w}}+\frac{iv}{w}
\end{aligned}
$$

转化成滑动窗口后用单调队列优化。

代码：

C++
#include<bits/stdc++.h>
using namespace std;

const int N=105,M=1e5+5;
int n,W;
int q[M],dp[N][M];

int main(){
    cin>>n>>W;
    for(int i=1;i<=n;i++){
        int v,w,m;
        cin>>v>>w>>m;
        for(int j=0;j<w;j++){
            int l=0,r=-1;
            for(int k=j;k<=W;k+=w){
                while(l<=r&&(k-q[l])/w>m) l++;
                if(l<=r) dp[i][k]=max(dp[i-1][k],dp[i-1][q[l]]+(k-q[l])/w*v);
                else dp[i][k]=dp[i-1][k];
                while(l<=r&&dp[i-1][q[r]]-q[r]*v/w<=dp[i-1][k]-k*v/w) r--;
                q[++r]=k;
            }
        }
    }
    cout<<dp[n][W];
    return 0;
}

P3195 [HNOI2008] 玩具装箱

斜率优化 DP 模板题。

先推转移方程，这里设 $sum$ 是 $C$ 的前缀和数组：

$$
dp_i=\min{dp_j+(i-j-1+sum_i-sum_j-L)^2}
$$

令 $A_i=sum_i+i,B_i=sum_j+j+L+1$，有：

$$
\begin{aligned}
dp_i&=\min{dp_j+(A_i-B_j)^2} \\
dp_i&=\min{-A_iB_j+B_j^2+dp_j}+A_i^2
\end{aligned}
$$

这是我们把每个 $(B_j,B_j^2+dp_j)$ 作为一个点加入平面直角坐标系，对于一次询问，相当于查询经过每个点的斜率为 $A_i$ 的直线的斜率最大是多少。

观察这幅图，对于任何斜率，可能产生贡献的点一定在凸包上，并且链接这个点的两条线一个斜率小于查询斜率，一个斜率大于查询斜率，这其实我们使用单调队列，每次查询后弹出队列内斜率小于当前斜率的点，加点时维护下凸包。

代码：

C++
#include<bits/stdc++.h>
using namespace std;

using ll=long long;
const int N=5e4+5;
ll n,L,l=1,r;
ll a[N],dp[N],q[N];
struct node{
    ll x,y;
}d[N];

__int128 mul(node a,node b,node c){
    __int128 x1=b.x-a.x,y1=b.y-a.y,x2=c.x-b.x,y2=c.y-b.y;
    return x1*y2-x2*y1;
}

signed main(){
    cin>>n>>L;
    for(int i=1;i<=n;i++) cin>>a[i],a[i]+=a[i-1];
    d[0]={L+1,(L+1)*(L+1)};
    q[++r]=0;
    for(int i=1;i<=n;i++){
        ll A=i+a[i],B=i+a[i]+1+L;
        while(l<r&&(__int128(d[q[l+1]].y-d[q[l]].y))<=__int128(2*A*(d[q[l+1]].x-d[q[l]].x))) l++;
        dp[i]=A*A+d[q[l]].y-2*A*d[q[l]].x;
        d[i].x=B,d[i].y=B*B+dp[i];
        while(l<r&&mul(d[q[r-1]],d[q[r]],d[i])<=0) r--;
        q[++r]=i;
    }
    cout<<dp[n];
    return 0;
}

P2900 [USACO08MAR] Land Acquisition G

先去掉那些被偏序了的点，之后不难想到一定是把一段排序后连续的区间放在一起购买，得到转移方程：

$$
dp_i=\min{dp_j+y_{j+1}*x_{i}}
$$

一眼斜率优化，但是这里展示高科技：李超线段树。

每次求 $x_i$ 这个位置的最小值，并插入一条新直线。

代码：

C++
#include<bits/stdc++.h>
using namespace std;
#define int long long
#define lc p<<1
#define rc p<<1|1

const int N=5e4+5;
const int M=1e6+5;
const int INF=2e18;
int n,m;
int dp[N];

struct land{
    int w,l;
    bool operator<(const land &o)const{
        if(w!=o.w) return w<o.w;
        return l<o.l;
    }
}p[N],a[N];

struct line{
    int k,b;
}lne[N];

struct tree{
    int l,r,ln;
}tr[M<<2];

int f(int id,int x){
    if(!id) return INF;
    return lne[id].k*x+lne[id].b;
}

void build(int p,int l,int r){
    tr[p].l=l,tr[p].r=r;
    if(l==r) return;
    int mid=(l+r)>>1;
    build(lc,l,mid);
    build(rc,mid+1,r);
}

void upd(int p,int x){
    int mid=(tr[p].l+tr[p].r)>>1;
    if(f(x,mid)<f(tr[p].ln,mid)) swap(tr[p].ln,x);
    if(tr[p].l==tr[p].r) return;
    if(f(x,tr[p].l)<f(tr[p].ln,tr[p].l)) upd(lc,x);
    else if(f(x,tr[p].r)<f(tr[p].ln,tr[p].r)) upd(rc,x);
}

int qry(int p,int x){
    if(tr[p].l==tr[p].r) return f(tr[p].ln,x);
    int mid=(tr[p].l+tr[p].r)>>1;
    int res=f(tr[p].ln,x);
    if(x<=mid) return min(res,qry(lc,x));
    else return min(res,qry(rc,x));
}

signed main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    cin>>n;
    for(int i=1;i<=n;i++) cin>>p[i].w>>p[i].l;
    sort(p+1,p+n+1);
    for(int i=1;i<=n;i++){
        while(m&&a[m].l<=p[i].l) m--;
        a[++m]=p[i];
    }
    build(1,1,1000000);
    lne[1]={a[1].l,0};
    upd(1,1);
    for(int i=1;i<=m;i++){
        dp[i]=qry(1,a[i].w);
        if(i<m){
            lne[i+1]={a[i+1].l,dp[i]};
            upd(1,i+1);
        }
    }
    cout<<dp[m]<<"\n";
    return 0;
}

P5785 [SDOI2012] 任务安排

这题的特殊点就是询问不是单调的，所以我们要保留凸包上的所有点，询问时在凸包上二分即可。

代码：

C++
#include<bits/stdc++.h>
using namespace std;

#define int long long
const int N=3e5+5;
int n,s,r;
int t[N],c[N],q[N],dp[N];

int find(int k){
    int l=1,rr=r;
    while(l<rr){
        int mid=(l+rr)>>1;
        if(dp[q[mid+1]]-dp[q[mid]]<=k*(c[q[mid+1]]-c[q[mid]])) l=mid+1;
        else rr=mid;
    }
    return q[l];
}

signed main(){
    ios::sync_with_stdio(0);
    cin.tie(0),cout.tie(0);
    cin>>n>>s;
    for(int i=1;i<=n;i++){
        cin>>t[i]>>c[i];
        t[i]+=t[i-1],c[i]+=c[i-1];
    }
    q[++r]=0;
    for(int i=1;i<=n;i++){
        int j=find(t[i]+s);
        dp[i]=dp[j]+t[i]*(c[i]-c[j])+s*(c[n]-c[j]);
        while(r>=2&&(dp[i]-dp[q[r]])*(c[q[r]]-c[q[r-1]])<=(dp[q[r]]-dp[q[r-1]])*(c[i]-c[q[r]])) r--;
        q[++r]=i;
    }
    cout<<dp[n]<<"\n";
    return 0;
}

CF321E Ciel and Gondolas

设 $c_{i,j}$ 表示第 $i$ 个人到第 $j$ 个人的陌生度之和，显然是等于 $u_{i,i}$ 加到 $u_{j,j}$ 再除以 $2$，可以通过二维前缀和求的的，并且 $c_{i,j}$ 满足四边形不等式。

设 $dp_{i,j}$ 表示选了 $i$ 组，共 $j$ 人的最小方案数，得到转移方程：

$$
dp_{i,j}=\min{dp_{i-1,k}+w(k+1,j)}
$$

显然是满足决策单调性的，就可以进行优化。

代码：

C++
#include<bits/stdc++.h>
using namespace std;

#define int long long
const int N=4e3+5,M=805;
int n,k;
int a[N][N],d[M][N],dp[M][N];

int read(){
    int k=0,f=1;
    char c=getchar();
    while(c<'0'||c>'9'){
        if(c=='-') f=-1;
        c=getchar();
    }
    while(c>='0'&&c<='9') k=k*10+c-'0',c=getchar();
    return k*f;
}

void put(int x){
    if(x<0) putchar('-'),x=-x;
    if(x<10) putchar(x+'0');
    else put(x/10),putchar(x%10+'0');
}

int w(int l,int r){
    return (a[r][r]-a[r][l-1]-a[l-1][r]+a[l-1][l-1])>>1;
}

signed main(){
    n=read(),k=read();
    for(int i=1;i<=n;i++) for(int j=1;j<=n;j++) a[i][j]=read();
    for(int i=1;i<=n;i++) for(int j=1;j<=n;j++) a[i][j]+=a[i][j-1]+a[i-1][j]-a[i-1][j-1];
    memset(dp,0x3f,sizeof dp);
    dp[0][0]=0;
    for(int i=1;i<=k;i++){
        d[i][n+1]=n;
        for(int j=n;j>=1;j--){
            int mn=dp[i][j],id;
            for(int l=d[i-1][j];l<=d[i][j+1];l++)
                if(dp[i-1][l]+w(l+1,j)<mn)
                    mn=dp[i-1][l]+w(l+1,j),id=l;
            dp[i][j]=mn,d[i][j]=id;
        }
    }
    put(dp[k][n]);
    return 0;
}