ZR 集训 Day14 – 动态规划与动态规划常见优化方法

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

AI 摘要

建邮局还能有这种操作？引入一个虚构的常数作为代价，二分它就能精准控制邮局数量，把受限 DP 变成无限制 DP——这就是 WQS 二分的魔力。再加上根号分治压状态、决策单调性砍复杂度，日间动态规划这些优化，一次看个透。

ZR 集训 Day14 - 动态规划与动态规划常见优化方法

前言

今天转 B 班了，题目比较神秘。

P2150 [NOI2015] 寿司晚宴

考虑枚举两个人所选数字的质因子集合。但是 $500$ 以内的素数很多，这时想到根号分治，$500$ 以内的数只会有一个大于 $22$ 的质因数，所以我们把这个质因数单拎出来。$22$ 以内的素数只有 $8$ 个，很好状压。我们把大质因数相等的数放在一起，对于这些数做一个 DP，用两个数组分别表示两个人谁选这些大素数。记得要减去两人都不选的情况。

代码：

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

const int N=505,M=305;
int n,mod,ans;
int dp[M][M],f1[M][M],f2[M][M];
int prm[]={2,3,5,7,11,13,17,19};
struct node{
    int p,k;
    bool operator<(const node b)const{
        return p<b.p;
    }
}a[N];

signed main(){
    cin>>n>>mod;
    for(int i=2;i<=n;i++){
        int x=i;
        for(int j=0;j<8;j++){
            if(x%prm[j]==0){
                a[i].k+=(1<<j);
                while(x%prm[j]==0) x/=prm[j];
            }
        }
        a[i].p=x;
    }
    sort(a+2,a+1+n);
    dp[0][0]=1;
    for(int i=2;i<=n;i++){
        if(a[i].p==1||a[i].p!=a[i-1].p||i==2){
            memcpy(f1,dp,sizeof dp);
            memcpy(f2,dp,sizeof dp);
        }
        for(int s1=(1<<8)-1;s1>=0;s1--) for(int s2=(1<<8)-1;s2>=0;s2--){
            if(s1&s2) continue;
            if((s1&a[i].k)==0) (f1[s1][s2|a[i].k]+=f1[s1][s2])%=mod;
            if((s2&a[i].k)==0) (f2[s1|a[i].k][s2]+=f2[s1][s2])%=mod;
        }
        if(a[i].p==1||a[i].p!=a[i+1].p||i==n){
            for(int s1=(1<<8)-1;s1>=0;s1--) for(int s2=(1<<8)-1;s2>=0;s2--){
                if(s1&s2) continue;
                (dp[s1][s2]=(f1[s1][s2]+f2[s1][s2]-dp[s1][s2])%mod+mod)%=mod;
            }
        }
    }
    for(int s1=(1<<8)-1;s1>=0;s1--) for(int s2=(1<<8)-1;s2>=0;s2--){
        if(s1&s2) continue;
        (ans+=dp[s1][s2])%=mod;
    }
    cout<<ans;
    return 0;
}

P6246 [IOI 2000] 邮局 加强版 加强版

WQS 二分+决策单调性优化。

什么是 WQS 二分？

我们设 $g(x)$ 表示建立 $x$ 个邮局所需的代价，发现该函数满足斜率单调，也就是 $g(x)-g(x-1)>=g(x+1)-g(x)$（这里可以感性理解一下，建 $2$ 个邮局相较于建 $1$ 个邮局代价的变化肯定不少于建 $100$ 个邮局相较于建 $99$ 个邮局代价的变化）。

这是我们先不考虑邮局数量的限制，并引入一个常数 $C$，表示新建一个邮局的代价，就可以得到新的一维 DP 式子：

dpi=min{dpj+w(j+1,i)+C}dp_i=min\{dp_j+w(j+1,i)+C\}

其中 $w(i,j)$ 表示在区间 $[i,j]$ 内新建一个邮局的最小代价。

那此时对于一个 $C$ 我们做 DP，会发现：当 $C$ 越大时，最优解建的邮局越少；当 $C$ 越小时，最优解建的邮局越多（这个感性理解一下还是很容易的）。此时我们不妨二分 $C$，找到最大的 $C$ 使得最优策略刚好建了 $m$ 个邮局，那答案就应该是 $dp_n-C\times m$。

以上就是 WQS 二分的过程了，相当于我们虚构了一个常数出来辅助我们。注意它的使用范围是在原函数是凸函数的情况下。

那么以上就是解决这道题的主要步骤了，对于二分的 check，我们需要对于当前的 $C$ 写一个 DP，不难发现其满足决策单调性，用单调队列+二分优化即可。

代码：

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

#define int long long
const int N=5e5+5;
int n,m;
int a[N],dp[N],sum[N],cnt[N],q[N],opt[N];

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

int calc(int l,int r,int c){
    return dp[l]+w(l+1,r)+c;
}

int bound(int x,int y,int c){
    int l=y,r=n,res=y-1;
    while(l<=r){
        int mid=(l+r)>>1;
        if(calc(x,mid,c)>=calc(y,mid,c)) r=mid-1;
        else res=mid,l=mid+1;
    }
    return res;
}

int check(int c){
    memset(dp,0,sizeof dp);
    memset(q,0,sizeof q);
    memset(opt,0,sizeof opt);
    int l=1,r=1;
    for(int i=1;i<=n;i++){
        while(l<r&&opt[l]<i) l++;
        dp[i]=calc(q[l],i,c),cnt[i]=cnt[q[l]]+1;
        while(l<r&&opt[r-1]>=bound(q[r],i,c)) r--;
        opt[r]=bound(q[r],i,c),q[++r]=i;
    }
    return cnt[n];
}

signed main(){
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++) scanf("%d",a+i);
    sort(a+1,a+1+n);
    for(int i=1;i<=n;i++) sum[i]=a[i]+sum[i-1];
    int l=0,r=1e9,ans;
    while(l<=r){
        int mid=(l+r)>>1;
        if(check(mid)>=m) l=mid+1,ans=dp[n]-m*mid;
        else r=mid-1;
    }
    printf("%lld",ans);
    return 0;
}