CCPC Wannafly Winter Camp Day4 Div2-DP 简要笔记

背包类

  • 01背包直接暴搜dfs(x,y,z)表示[1,x]装了体积y最大价值z时间复杂度O(2^n),但我们如果把状态记下来进行DP就能优化至O(nm),暴搜->DP
  • 01背包计数,i从大到小更新f[i]+=f[i-v]删除i从小到大更新f[i]-=f[i-v]相当于是一个逆过程,因为加入物品的顺序不影响结果,所以假设被删除的物品是最后一次加入的,那么倒过来还原即可,删除物品的技巧也可以拓展到完全背包。
  • 用生成函数去看待背包:2018沈阳区域赛M的题意是给定n个物品,每个物品价值为a_i,数量为b_iq次询问区间[L,R]c元购买物品的方案数。我们可以这样来看待多重背包,我们把它用生成函数表示,即\sum_{i=0}^{b_i}x^{a_i}=\frac{1-x^{a_i(b_i+1)}}{1-x^{a_i}}其实区间的背包方案数就是[L,R]每个生成函数乘起来以后x^{i}(i\le c)的所有系数之和,这样看貌似还看不出什么优化的地方。考虑到物品加入的顺序不影响结果,我们可以先求出[1,R]的生成函数乘积,然后再除以[1,L-1]生成函数的乘积就可以得到我们要的了,除以我们可以利用前面的公式看成\frac{1-x^{a_i}}{1-x^{a_i(b_i+1)}},那么这个和式的意义是什么?1-x^c其实就是01背包的删除,而\frac{1}{1-x^a}=\sum_{x=0}^{inf}x^a,这样其实就相当于完全背包的生成函数,所以一个多重背包物品的加入其实等价于一个完全背包物品的加入和一个01背包物品的删除,我们预处理出生成函数前缀乘积和前缀逆即可,然但是注意这样你把两个[1,L-1][1,R]的生成函数乘起来得到的x^c是恰好加起来等于c元的方案数,而不是\le c的方案数,所以合并时间复杂度还是O(c^2)的,你可能会说用FFT去做,因为其实是相当于两个多项式卷积,但这样。。。常数很大应该过不去,其实解决办法也很简单,只要再乘上一个生成函数\sum_{i=0}x^ix^c的系数就是前缀和了,自己拿两个多项式模拟一下感受一下就知道了。。。这样预处理复杂度是O(nm),询问复杂度O(qc),总时间复杂度O(nm+qc)可以通过。
#include<bits/stdc++.h>
#define MP make_pair
#define PB emplace_back
using namespace std;
typedef long long ll;
template<typename T>
inline T read(T&x){
    x=0;int f=0;char ch=getchar();
    while (ch<'0' || ch>'9') f|=(ch=='-'),ch=getchar();
    while (ch>='0'&& ch<='9') x=x*10+ch-'0',ch=getchar();
    return x=f?-x:x;
}
const int N=10000+10;
const int M=1000+10;
const int P=1e9+7;
int T,cas=1,n,m,i,j,ans,L,R,c,a[N],b[N],f[N][M],g[N][M];
inline void up(int&a,int b){a+=b==P?0:b;if(a>=P)a-=P;}
int main(){
    f[0][0]=1;
    for (i=0;i<=M;++i) g[0][i]=1;
    for (read(T);T--;){
        read(n),read(m);
        for (i=1;i<=n;++i) read(a[i]),read(b[i]),a[i]=(a[i]+1)*b[i];
        printf("Case #%d:\n",cas++);
        for (i=1;i<=n;++i){
            for (j=0;j<=M-10;++j) f[i][j]=f[i-1][j],g[i][j]=g[i-1][j];
            for (j=M-10;j>=a[i];--j) up(f[i][j],P-f[i][j-a[i]]);
            for (j=b[i];j<=M-10;++j) up(f[i][j],f[i][j-b[i]]);
            for (j=M-10;j>=b[i];--j) up(g[i][j],P-g[i][j-b[i]]);
            for (j=a[i];j<=M-10;++j) up(g[i][j],g[i][j-a[i]]);
        }
        for (ans=0,i=1;i<=m;++i){
            read(L),read(R),read(c);
            L=(L+ans)%n+1,R=(R+ans)%n+1;
            if (L>R) swap(L,R);
            for (ans=0,j=0;j<=c;++j) up(ans,1LL*f[R][j]*g[L-1][c-j]%P);
            printf("%d\n",ans);
        }
    }
    return 0;
}
  • 多重背包:暴力O(m\sum k),二进制拆分O(nmlogk),单调队列优化O(nm),计数的时候也可以用上面讲的生成函数的思想O(nm)。单调队列优化是把状态按照对物品的体积V_i相除后的余数进行分组,然后状态转移方程就可以写成F[u+p* V_i]=max(F[u+k* V_i]+(p-k)* W_i)(p-C_i\le k \le p-1)维护一个决策点k单调递减,F[u+k* V_i]-k* W_i单调递减的队列即可。
  • 分组背包(待理思路)
  • 树形依赖背包:按照dfs的顺序进行dp,定义f[i][j]为以i为根的子树里强行选了i的所有祖先且容量为j时所能获得的最大价值,每次往下搜索的时候先把父亲的dp值强行赋值给儿子然后让儿子继续dp,往上回溯的时候可以选择要这棵子树的dp值也可以不要,合并的复杂度是O(m)的,总时间复杂度是O(nm)
    • 例题:P1273 有线电视网
    • 思路:叶子节点体积为1非叶子节点体积为0,边的价值直接扔给深度较深的节点,进行树形背包dp最后看价值大于0的体积最大的是哪个就可以了。
const int N=3000+10;
int n,m,i,j,k,a,c,ans,leaf[N],val[N],f[N][N];
vector<int>G[N];
void dfs(int u,int num){
    for (int i=0;i<(int)G[u].size();++i){
        int v=G[u][i];
        for (int j=num+leaf[v];j<=n;++j) f[v][j]=f[u][j-leaf[v]]+val[v];
        dfs(v,num+leaf[v]);
        for (int j=0;j<=n;++j) f[u][j]=max(f[u][j],f[v][j]);
    }
}
int main(){
    read(n),read(m);
    for (i=1;i<=n-m;++i){
        read(k);
        for (;k--;){
            read(a),read(c);
            G[i].PB(a);
            val[a]-=c;
        }
    }
    for (i=n-m+1;i<=n;++i){
        read(c);
        val[i]+=c;
        leaf[i]=1;
    }
    for(i=1;i<=n;++i)for(j=0;j<=n;++j)f[i][j]=-2000000000;
    f[1][0]=0;
    dfs(1,0);
    for (i=1;i<=n;++i){
        if (f[1][i]>=0) ans=i;
    }
    printf("%d\n",ans);
    return 0;
}

LIS

  • 暴力DP反正O(n^2),但我们考虑DP的式子就可以发现直接用树状数组维护可以降到O(nlogn)
  • 还有一种贪心的思路就是维护一个队列数组,然后每次加入一个数如果这个数比末尾的数要大的话就直接加入,否则二分查找数组里大于等于这个数的最小的位置然后替换成这个数,这样的话可以认为这个队列数组更具备增加答案的潜力,最后的答案就是队列数组里元素的个数,时间复杂度也是O(nlogn)
  • 扩展:k-LIS问题:给定一个长度为n的序列a_1,a_2,\cdots,a_n,从中选出k个递增子序列,使得总长度最大,具体做法课件里有就不赘述了直接把BZOJ1175也就是k-LIS的代码放出来。
#include <bits/stdc++.h>
#define MP make_pair
#define PB emplace_back
using namespace std;
typedef long long ll;
template<typename T>
inline T read(T&x){
    x=0;int f=0;char ch=getchar();
    while (ch<'0' || ch>'9') f|=(ch=='-'),ch=getchar();
    while (ch>='0' && ch<='9') x=x*10+ch-'0',ch=getchar();
    return x=f?-x:x;
}
const int N=5000+10;
int n,i,x,t[N],q[N][N];
void up(int p,int x){
    if (x>=q[p][t[p]]){
        q[p][++t[p]]=x;
        return;
    }
    int l=1,r=t[p],u;
    while (l<=r){
        int mid=l+((r-l)>>1);
        if (q[p][mid]>x){
            u=mid;
            r=mid-1;
        }
        else l=mid+1;
    }
    up(p+1,q[p][u]),q[p][u]=x;
}
int main(){
    read(n);
    for (i=1;i<=n;++i) read(x),up(1,x);
    for (i=1;;++i){
        printf("%d\n",t[i]+=t[i-1]);
        if (t[i]==n) break;
    }
    return 0;
}
  • 关于LIS的题目,很多需要先根据题目条件列个式子,然后进行化简,最后可能需要进行什么坐标变换然后就可以转化为这个问题了,课件的例题免费的馅饼以及题解报告

发表评论

电子邮件地址不会被公开。 必填项已用*标注