DP训练——状压DP

作者: 云中翻月 | 来源:发表于2020-02-24 15:52 被阅读0次

状压DP

BZOJ1087
题意
在 $n*n(n<=9)$ 的棋盘里面放 $K$ 个国王，使他们互不攻击，共有多少种摆放方案。国王能攻击到它上下左右，以及左上左下右上右下八个方向上附近的各一个格子，共 $8$ 个格子。
题解
根据国王的攻击特性，若采用按行dp的方式，每一行的状态只与上一行的状态有关。
预处理出每行的所有合法状态，发现最多只有不超过 $100$ 个，所以时间复杂度为 $n*K*100*100$ ，能承受。
状态定义： $f[i,j,k]$ 表示当前处理到第 $i$ 行，第 $i$ 行的落子情况为 $j$ ，当前共落子 $k$ 枚的方案数
目标： $\sum_{j为所有合法状态}f[n,j,K]$
边界： $f[0,0,0]=1$
转移方程： $f[i,j,k]=\sum_{pj为上一行的状态且j与pj不冲突，tot为第i行落子的个数}f[i-1,pj,k-tot]$
PS：关于dp四重循环的顺序
先两重循环枚举当前状态，第三重循环枚举当前行落子数（dp中的决策），然后再用一重循环，枚举上一层的状态进行转移。
代码如下

/*

*/
#define method_1
#ifdef method_1
/*

*/
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cmath>
#include<set>
#include<map>
#include<queue>
#include<stack>
#include<vector>
#include<cstring>
#include<cstdlib>
#include<iomanip>
#include<ctime>
#include<string>
#include<bitset>
#define D(x) cout<<#x<<" = "<<x<<"  "
#define E cout<<endl
using namespace std;
typedef long long ll;
typedef pair<int,int>pii;
const int maxn=9+2;
const int INF=0x3f3f3f3f;
int n,K;
ll f[maxn][(1<<maxn)][maxn*maxn]; //f[i,j,k]表示当前处理到第i行 第i行的落子情况为j 当前共落子k枚的方案数
ll ans=0;
int vis[(1<<maxn)],cnt=0;
bool check(int x){ //判断x的二进制中 是否存在连续的1 不存在则返回true
    int last=0;
    while(x){
        int temp=x&1;
        if(temp==1&&last==1) return false;
        last=temp;
        x>>=1;
    }
    return true;
}
bool check1(int x,int y){ //判断一行状态为x 一行状态为y是否冲突 不冲突则返回true
    if(x&y) return false;
    if((x>>1)&y) return false;
    if((x<<1)&y) return false;
    return true;
}
int num(int x){ //求x的二进制中1的个数
    int res=0;
    for(int i=x;i>=1;i-=i&-i) res++;
    return res;
}
void pre(int n){ //预处理一行所有合法的状态
    for(int i=0;i<(1<<n);i++) if(check(i)) vis[++cnt]=i;
//    D(cnt); //n=9 cnt=89
//    for(int i=1;i<=cnt;i++) D(vis[i]);
}
void dp(){
    f[0][0][0]=1;
    for(int i=1;i<=n;i++){
        for(int j=1;j<=cnt;j++){
            int tot=num(vis[j]);
            for(int k=tot;k<=K;k++){
                for(int pj=1;pj<=cnt;pj++){
                    if(num(vis[pj])>k-tot) continue;
                    if(!check1(vis[j],vis[pj])) continue;
                    f[i][vis[j]][k]+=f[i-1][vis[pj]][k-tot];
                }
            }    
        }
    }
    for(int i=1;i<=cnt;i++) ans+=f[n][vis[i]][K];
}
int main() {
    ios::sync_with_stdio(false);
    //freopen("BZOJ1087.in","r",stdin);
    cin>>n>>K;
    pre(n);
    dp();
    cout<<ans;
    return 0;
}
#endif
#ifdef method_2
/*

*/

#endif
#ifdef method_3
/*

*/

#endif

BZOJ3195
题意
$n(n<=30)$ 个城市， $m$ 条边 $(m<=30)$ 构成无自环的无向图.
城市间道路满足相连城市编号绝对值差小于等于 $K(K<=8)$ ，且任何一个城市都与恰好偶数条道路相连，求城市道路分布的方案数（结果须取模）。
题解
首先，数据范围虽小，但答案需要对一个大素数取模，因此搜索方法不在考虑范围内。
其次，考虑dp的设计。题目中城市间道路的要求有两个，绝对值之差小于等于 $K$ 和任何一个城市都与恰好偶数条道路相连。
因此，可以在dp到第 $i$ 个城市时，记录 $[i,i-K]$ 共 $K+1$ 个城市所连道路的奇偶性，通过枚举第 $i$ 个城市向前的连边情况来完成状态转移。
状态定义： $f[i,j,k]$ 表示已经处理到第 $i$ 个城市，连了 $j$ 条边， $[i-K,i]$ 共 $K+1$ 个城市的奇偶性为 $k$ 的方案数(偶数为 $0$ ，奇数为 $1$ ，右边为低位，左边为高位)
目标： $f[n,m,0]$
边界： $f[1,0,0]=1$
转移方程：
分为两种情况考虑， $i$ 点向前 $K$ 个点连边，或者直接转移到第 $i+1$ 个点（第二种转移的前提是第 $i-K$ 个点的连边已为偶数）
具体转移方程较为繁琐，实现见代码。
PS：
实现过程中，须注意通过改变枚举的顺序，来避免连边顺序不同而导致的重复计数。
同时由于根据当前状态计算上一个状态的二进制表示较为困难，但可以较为容易的计算下一个状态，所以dp采用了刷表法。
具体详见代码注释。
题解链接
http://www.suoniao.com/article/23702
https://blog.csdn.net/qq_33229466/article/details/72793603
代码如下

/*

*/
#define method_1
#ifdef method_1
/*

*/
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cmath>
#include<set>
#include<map>
#include<queue>
#include<stack>
#include<vector>
#include<cstring>
#include<cstdlib>
#include<iomanip>
#include<ctime>
#include<string>
#include<bitset>
#define D(x) cout<<#x<<" = "<<x<<"  "
#define E cout<<endl
using namespace std;
typedef long long ll;
typedef pair<int,int>pii;
const int maxn=30+5;
const int maxm=30+5;
const int maxK=8+2;
const int INF=0x3f3f3f3f;
const ll mod=1000000007;
int n,m,K;
ll f[maxn][maxm][(1<<maxK)]; 
//f[i,j,k]表示已经处理到第i个城市 连了j条边 [i-K,i]共K+1个城市的奇偶性为k的方案数(偶数为0 奇数为1 右边为低位 左边为高位)
void dp(){
    f[1][0][0]=1;
    for(int i=1;i<=n;i++){
        //从i向前面的点建边
        for(int l=max(1,i-K);l<=i-1;l++){  //先枚举与i相连的点，避免状态的重复枚举
            for(int j=1;j<=m;j++){  //再进行转移
                for(int k=0;k<(1<<K+1);k++){ //枚举连边之前的状态
                    if(!f[i][j-1][k]) continue;
                    int nxt_k=k^(1<<i-l)^1; //(1<<i-l)^1表示加入一条l和i的边(1<<i-l为l一头的端点，1为i一头的端点)
                    f[i][j][nxt_k]=(f[i][j][nxt_k]+f[i][j-1][k])%mod;
                }
            }
        }
        if(i==n) continue;
        //直接转移到第i+1个点
        for(int j=0;j<=m;j++){ 
            for(int k=0;k<(1<<K+1);k++){ //枚举[i-K,i]共K+1个城市的奇偶性     
                if((k&(1<<K))) continue; //第i-K个点必须要合法 才能转移 这样保证可能不合法的只有[i-K,i]共K+1个城市
                f[i+1][j][(k<<1)%(1<<K+1)]=(f[i+1][j][(k<<1)%(1<<K+1)]+f[i][j][k])%mod;
            }
        }
    }
}
int main() {
    ios::sync_with_stdio(false);
    //freopen("BZOJ3195.in","r",stdin);
    cin>>n>>m>>K;
    dp();
    cout<<f[n][m][0];
    return 0;
}
#endif
#ifdef method_2
/*

*/

#endif
#ifdef method_3
/*

*/

#endif

BZOJ1226
题意
$n(n<=1000)$ 个人，排队吃饭，每个人都有各自的口味要求，制作一份饭需要的时间取决于这份饭的口味和上一份饭的口味的异或值。
食堂可以调整排队顺序，但第 $i$ 个人最多忍受紧跟在他后边的 $B_i(B_i<=7)$ 个人先于他吃饭，求最少做饭时间。
题解
$B_i$ 的范围很小，因此可以考虑使用状态压缩的方式记录每个人前后人的吃饭情况，从而进行dp。
状态定义： $f[i,j,k]$ 表示处理到第 $i$ 个人（前 $i-1$ 个人已经吃完）， $[i,i+7]$ 的吃饭状态为 $j$ （ $i+7$ 是j的最高位， $i$ 是 $j$ 的最低位），且最后一个吃饭的人是 $i+k$ 的最短时间。 $-8<=k<=7$
目标： $min(f[n+1,0,-8],...,f[n+1,0,-1])$
边界： $f[1,0,-1]=0$
转移方程：
分两种情况讨论。
1. $i$ 已经吃饭，则可以从 $f[i,j,k]$ 转移到 $f[i+1,j>>1,k]$ 。这时不会产生代价，因为 $j$ 里已经包含 $i$ 了。
2. $i$ 没有吃饭，则可以枚举下一个吃饭的人，即可以从 $f[i,j,k]$ 转移到 $f[i,j|(1<<l),l]$ （ $0<=l<=7,(1<<l)\&j==0$ ，因为根据状态定义，i之前的已经吃过），这时会产生 $(t[k]|t[l])-(t[k]\&t[l])$ 的代价。
PS：由于这里的 $k$ 存在负数的情况，所以要在所有涉及dp数组第三维运算的时侯加上 $base=8$ 。
代码如下

/*

*/
#define method_1
#ifdef method_1
/*

*/
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cmath>
#include<set>
#include<map>
#include<queue>
#include<stack>
#include<vector>
#include<cstring>
#include<cstdlib>
#include<iomanip>
#include<ctime>
#include<string>
#include<bitset>
#define D(x) cout<<#x<<" = "<<x<<"  "
#define E cout<<endl
using namespace std;
typedef long long ll;
typedef pair<int,int>pii;
const int maxn=1000+5;
const int maxb=8+2;
const int base=8;
const int INF=0x3f3f3f3f;
int T;
int n,t[maxn],b[maxn];
int f[maxn][(1<<maxb)][(maxb<<1)];
int ans;
void init(){
    memset(f,INF,sizeof(f));
    ans=INF;
}
int sum(int x,int y){
    if(x==0) return 0; //注意这里要特判做第一道菜的情况
    return (t[x]|t[y])-(t[x]&t[y]);
}
void dp(){
    f[1][0][-1+base]=0;
    for(int i=1;i<=n;i++){
        for(int j=0;j<(1<<base);j++){
            for(int k=-base;k<=base-1;k++){
                if(f[i][j][k+base]==INF) continue;
                if(i+k+base<1) continue;
                if(j&1){ //i已吃饭
                    f[i+1][j>>1][k-1+base]=min(f[i+1][j>>1][k-1+base],f[i][j][k+base]);
                }
                else{ //i未吃饭
                    int lim=INF;
                    for(int l=0;l<=base-1;l++){
                        if(j&(1<<l)) continue;
                        if(i+l>lim) break;
                        lim=min(lim,i+l+b[i+l]);//让i+l在i之前吃饭，则必须满足[i,i+l-1]所有人的忍受能力限制
                        f[i][j|(1<<l)][l+base]=min(f[i][j|(1<<l)][l+base],f[i][j][k+base]+sum(i+k,i+l));
//                        D(sum(t[i+k],t[i+l]));
//                        D(f[i][j|(1<<l)][l+base]);E;
                    }
                }
            }
        }
    }
    for(int k=-base;k<=-1;k++) ans=min(ans,f[n+1][0][k+base]);
}
int main() {
    ios::sync_with_stdio(false);
    //freopen("BZOJ1226.in","r",stdin);
    cin>>T;
    while(T--){
        cin>>n;
        for(int i=1;i<=n;i++) cin>>t[i]>>b[i];
        init();
        dp();
        cout<<ans<<endl;
    }
    return 0;
}
#endif
#ifdef method_2
/*

*/

#endif
#ifdef method_3
/*

*/

#endif

BZOJ4197
题意
$n-1(n<=500)$ 个物品，价值依次为 $2...n$ 。两人可以各自从中选出一个集合，求选出的两个集合间所有数互质的方案数。
题解
要让两个人选的数字全部互质，那么有一个显然的充要条件：甲选的数字的质因数集合和乙选的数字的质因数集合没有交集。
因此考虑进行如下状态定义
$f[i,j,k]$ 表示处理完前 $i$ 个物品，甲选择的质因数集合是 $j$ ，乙是 $k$ 的总情况数
转移时枚举第 $i$ 个数加入哪个集合即可。
时间复杂度 $O(n*2^{n的质因数个数})$
空间复杂度 $O(n*2^{n的质因数个数})$
通过类似01背包的思想（因为每个质因数最多被选择一次），可以改变枚举 $j$ 和 $k$ 的顺序来压缩第一维，从而降低空间复杂度到可接受的程度。
接下来考虑时间复杂度。
注意到，一个小于 $500$ 的数，最多只可能有 $1$ 个比 $22$ 大的质因子。
所以我们可以把这个质因子单独拿出来记录一下。
然后，我们把 $2-n$ 这些数按照大质因子大小排序，这样令大质因子相同的数排在一起。（也就是不能甲乙同时选的）
状态定义：
$f[j,k]$ 表示甲选择的质因数集合是 $j$ ，乙选择的质因数集合是 $k$ 的总情况数
$d[j,k,0]$ 表示当前数的大质因子让第一个人选的总情况数
$d[j,k,1]$ 表示当前数的大质因子让第二个人选的总情况数
目标： $\sum_{0\leq j \leq 255 \; \& \; 0\leq k \leq 255}f[j,k]$
边界： $f[0,0]=1$
转移方程：
分为三步考虑。
对于每一段大质因子不同的数，我们在这一段开始的时候把 $f$ 的值赋给 $d[,,0]$ 和 $d[,,1]$ 。
然后在这一段内部用刷表法推 $d[,,0]和d[,,1]$ 。
$d[j|num[i],k,0]=d[j,k,0]+d[j|num[i],k,0]$
$d[j,k|num[i],1]=d[j,k,1]+d[j,k|num[i],1]$
这一段数推完以后，若当前阶段和下个阶段大质因子不同，再把 $d[,,0]$ 和 $d[,,1]$ 合并到 $f$ 里面即可。
$f[j,k]=d[j,k,0]+d[j,k,1]-f[j,k]$
这里减掉一个dp是因为两种情况会重复统计两个人都不选的情况（也就是原来的 $f[j,k]$ 的值），减掉即可。
代码如下

/*

*/
#define method_1
#ifdef method_1
/*

*/
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cmath>
#include<set>
#include<map>
#include<queue>
#include<stack>
#include<vector>
#include<cstring>
#include<cstdlib>
#include<iomanip>
#include<ctime>
#include<string>
#include<bitset>
#define D(x) cout<<#x<<" = "<<x<<"  "
#define E cout<<endl
using namespace std;
typedef long long ll;
typedef pair<int,int>pii;
const int maxn=500+5;
const int maxl=256+5; //2^8
const int pn=8; //prime number
const int INF=0x3f3f3f3f;
const int prime[]={2,3,5,7,11,13,17,19}; //小于22的8个质数 
int n;
ll p;
ll f[maxl][maxl],d[maxl][maxl][2];
ll ans=0ll;
struct node{
    int s,big;
    bool operator<(const node& h)const{return big<h.big;} 
}num[maxn];
void init(){ //对n-1个物品分解质因数，并且记录每个数的最大质因子（如果该数没有大于22的质因子，则默认最大质因子为1）
    for(int i=1;i<=n-1;i++){
        int temp=i+1;
        num[i].s=0;
        for(int j=0;j<=7;j++){
            if(temp%prime[j]==0){
                while(temp%prime[j]==0) temp/=prime[j];
                num[i].s|=(1<<j);
            }
        }
        num[i].big=temp;
    }
    sort(num+1,num+n); //按照每个数的最大质因子升序排序
//    for(int i=1;i<=n-1;i++) cout<<num[i].big<<" "<<num[i].s<<endl;
}
void dp(){
    f[0][0]=1ll%p;
    for(int i=1;i<=n-1;i++){
        if(num[i].big==1||i==1||num[i].big!=num[i-1].big){ //从前面递推过来，所以是i与i-1比较
            for(int j=(1<<pn)-1;j>=0;j--) for(int k=(1<<pn)-1;k>=0;k--) d[j][k][0]=d[j][k][1]=f[j][k];
        }
        for(int j=(1<<pn)-1;j>=0;j--) for(int k=(1<<pn)-1;k>=0;k--){ //滚动数组，所以是倒序
            if((num[i].s&j)==0) d[j][k|num[i].s][1]=(d[j][k][1]+d[j][k|num[i].s][1])%p;
            if((num[i].s&k)==0) d[j|num[i].s][k][0]=(d[j][k][0]+d[j|num[i].s][k][0])%p;
        }
        if(num[i].big==1||i==n-1||num[i].big!=num[i+1].big){ //向后递推，所以是i和i+1比较
            for(int j=(1<<pn)-1;j>=0;j--) for(int k=(1<<pn)-1;k>=0;k--) f[j][k]=(d[j][k][0]+d[j][k][1]-f[j][k]+p)%p;
        }
    }
    for(int j=0;j<(1<<pn);j++) for(int k=0;k<(1<<pn);k++) if((j&k)==0) ans=(ans+f[j][k])%p;
}
int main() {
    ios::sync_with_stdio(false);
    //freopen("BZOJ4197.in","r",stdin);
    cin>>n>>p;
    init();
    dp();
    cout<<ans<<endl;
    return 0;
}
#endif
#ifdef method_2
/*

*/

#endif
#ifdef method_3
/*

*/

#endif

DP训练——状压DP

状压DP

相关文章

网友评论

延伸阅读

深度阅读

栏目导航

热点阅读

动态规划