状压DP学习总结（一）（看题总结）

66 阅读 0 评论 44 点赞

我是靠谱客的博主平淡往事，最近开发中收集的这篇文章主要介绍状压DP学习总结（一）（看题总结），觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

CodeForces 53 E.Dead Ends（状压DP）
题目：给出一个n个点m条边的无向连通图，问删掉若干边使得该图变成一个恰有K个叶子的树的方案数

#include<cstdio>
#include<iostream>
#include<cstring>
#include<algorithm>
#include<vector>
using namespace std;
typedef long long ll;
typedef pair<int,int>P;
const int INF=0x3f3f3f3f,maxn=1025;
int n,m,K;
//状态压缩，2的某一位表示当前状态
ll dp[maxn][maxn];//i表示当前图连通分量中的点的有无,有则为1,无则为0
//j表示当前位是否为叶子节点
vector<int>g[maxn];
//动态数组存储稀疏图,节省空间
int main()
{
scanf("%d%d%d",&n,&m,&K);
while(m--){
int u,v;
scanf("%d%d",&u,&v);
u--,v--;
g[u].push_back(v),g[v].push_back(u);
dp[(1<<u)^(1<<v)][(1<<u)^(1<<v)]=1;
//因为零图新增一个边,图置入两点,置入两个叶子节点.注意自环的边不能置入。
}
int N=1<<n;
for(int i=1;i<N;i++){
for(int j=1;j<=i;j++){
if((i&j)==j&&dp[i][j]){//必要!因为是叶子节点的点一定出现在图中
for(int x=0;x<n;x++){
if((i>>x)&1){//在图中的点x
for(int k=0;k<g[x].size();k++){//遍历x所有邻接点
int y=g[x][k];
if(!((i>>y)&1)){//y不再图中
//讨论x是否为叶子节点的情况.
//因加边顺序不同所以,可能导致重复,所以每次只能加入最大编号的.
if(((j>>x)&1)&&(j^(1<<x))<(1<<y))dp[i^(1<<y)][j^(1<<x)^(1<<y)]+=dp[i][j];//注意X比y大的情况.
else if(!((j>>x)&1)&&j<(1<<y))dp[i^(1<<y)][j^(1<<y)]+=dp[i][j];
}
}
}
}
}
}
}
int ans=0;
for(int i=1;i<N;i++)
{
int num=0;
for(int j=0;j<n;j++)
if((i>>j)&1)num++;
if(num==K)ans+=dp[N-1][i];//所有k个节点的累加
}
printf("%dn",ans);
return 0;
}

HDU 6149 Valley Numer II（状压DP）
如果一个顶点三元组<X,Y,Z> 中，X和Y之间有边，Y与Z之间也有边，同时X和Z是高点，Y是低点，那么它们就构成一个valley

度度熊想知道一个无向图中最多可以构成多少个valley，一个顶点最多只能出现在一个valley中。

#include<cstdio>
#include<cstring>
#include<algorithm>
#include<vector>
using namespace std;
typedef pair<int,int>P;
int T,n,m,k,low[31],high[16],dp[31][(1<<15)+5];
bool a[31][31],vis[31];
vector<P>g[31];//用来保存边
int main()
{
scanf("%d",&T);
while(T--){
scanf("%d%d%d",&n,&m,&k);
memset(a,0,sizeof(a));
while(m--){
int x,y;
scanf("%d%d",&x,&y);
a[x][y]=a[y][x]=1;
//题目重点是是否连通，可以直接开bool数组来存储图
}
//划分高低点
memset(vis,0,sizeof(vis));
for(int i=0;i<k;i++){
scanf("%d",&high[i]),vis[high[i]]=1;
}
int res=0;
for(int i=1;i<=n;i++) if(!vis[i])low[res++]=i;
for(int l=0;l<res;l++)
{
g[l].clear();
for(int i=0;i<k;i++){
if(a[low[l]][high[i]]){
for(int j=i+1;j<k;j++){
if(a[low[l]][high[j]]){
g[l].push_back(P(i,j));//保存可选的两个高点
}
}
}
}
}
memset(dp,0,sizeof(dp));
int K=1<<k;
for(int l=0;l<res;l++){
for(int s=0;s<K;s++){
dp[l+1][s]=max(dp[l+1][s],dp[l][s]);
for(int i=0;i<g[l].size();i++){
int x=g[l][i].first,y=g[l][i].second;
if((s&(1<<x))||(s&(1<<y)))continue;//状态s中，x不在且y不在
dp[l+1][s^(1<<x)^(1<<y)]=max(dp[l+1][s^(1<<x)^(1<<y)],dp[l][s]+1);
}
}
}
//遍历所有dp[k][s],s为所有状态.
int ans=0;
for(int s=0;s<K;s++)ans=max(ans,dp[res][s]);
printf("%dn",ans);
}
}

Codeforces 16E Fish (状压dp+概率)
题目：有n条鱼，他们相遇时会吃掉对方，给出他们相遇时双方获胜的概率，求这n条鱼最后剩下自己的概率。

#include<cstdio>
#include<iostream>
#include<cstring>
#include<algorithm>
#include<vector>
using namespace std;
typedef pair<int,int>P;
const int INF=0x3f3f3f3f,maxn=(1<<18)+5;
int n,f[maxn],num[maxn];
double a[20][20],dp[maxn];
int main()
{
num[0]=0;//一个状态中鱼的数量
for(int i=1;i<(1<<6);i++){
num[i]=num[i/2]+(i&1);
//cout<<i<<" "<<num[i]<<endl;
}
for(int i=0;i<18;i++) f[1<<i]=i;
scanf("%d",&n);
for(int i=0;i<n;i++){
for(int j=0;j<n;j++){
scanf("%lf",&a[i][j]);
}
}
int N=1<<n;
dp[N-1]=1;
for(int S=N-1;S>=0;S--){
//因为鱼数量状态相对减少或者说满足任何一种情况的拓扑序
if(num[S]>1){
int m=num[S]*(num[S]-1)/2;//总的可能情况Cm2,枚举情况
for(int i=0;i<n;i++){
if((S>>i)&1){
for(int j=i+1;j<n;j++){
if((S>>j)&1){
dp[S^(1<<j)]+=a[i][j]*dp[S]/m;
dp[S^(1<<i)]+=a[j][i]*dp[S]/m;
}
}
}
}
}
}
for(int i=0;i<n;i++){
printf("%.6f%c",dp[1<<i],i==n-1?'n':' ');
}
return 0;
}

题意：
给定n个物品，第i个物品的坐标为(xi,yi)，你的起点坐标为(xs,ys)。给定n个物品，第i个物品的坐标为(x_i,y_i)，你的起点坐标为(x_s,y_s)。给定n个物品，第i个物品的坐标为(x i,y i)，你的起点坐标为(xs,ys )。
现在要将所有物品全部放回起点，每次手中拿的物品数量不能超过2个。现在要将所有物品全部放回起点，每次手中拿的物品数量不能超过2个。现在要将所有物品全部放回起点，每次手中拿的物品数量不能超过2个。
从一个位置到另外一个位置花费的时间为距离的平方。问最少时间。从一个位置到另外一个位置花费的时间为距离的平方。问最少时间。从一个位置到另外一个位置花费的时间为距离的平方。问最少时间。
思路：状态压缩，拿走的状态为1，没有拿走状态为0

#include <bitsstdc++.h>
using namespace std;
int x[25], y[25], dis[25][25], path[1<<24];
int dp[1<<24];
int main()
{
int n;
cin >> x[0] >> y[0] >> n;
for(int i = 1 ; i <= n ; i++){
cin >> x[i] >> y[i];
}
for(int i = 0 ; i <= n ; i++){
for(int j = 0 ; j <= n ; j++){
dis[i][j] = (x[i]-x[j])*(x[i]-x[j])+(y[i]-y[j])*(y[i]-y[j]);//先行计算出两点距离
}
}
memset(dp, 0x3f, sizeof(dp));
dp[0] = 0;
for(int i = 0 ; i < (1<<n)-1 ; i++){
if(dp[i] < 0x3f3f3f3f){
for(int j = 0 ; j < n ; j++){
if(!(i>>j & 1)){
for(int k = j ; k < n ; k++){
if(!(i>>k & 1)){
if(dp[i | 1<<j | 1<<k] > dp[i]+dis[0][j+1]+dis[j+1][k+1]+dis[k+1][0]){
dp[i | 1<<j | 1<<k] = dp[i]+dis[0][j+1]+dis[j+1][k+1]+dis[k+1][0];
path[i | 1<<j | 1<<k] = i;
}
}
}
break;
//因为在要求不重复的情况下，所以先选取第一个,如果那两个另外一个不做要求
//在最优的情况下,先后拿哪个无所谓,因为所有点到原点总和不变.
//重点在于如何选取两个的组合,或者只选一个.
}
}
}
}
cout << dp[(1<<n)-1] << endl;
cout << 0;
for(int i = (1<<n)-1 ; i > 0 ; i = path[i]){
for(int j = i^path[i] ; j > 0 ; j -= j & -j){
cout << ' ' << (int)(log(j&-j)/log(2)+1e-8+1);
//i^path[i]之后只有这次拿走的一个或者两个点上为1，其余为0。
//先输出到原点距离近的,在输出到原点距离远的.
}
cout << ' ' << 0;
}
return 0;
}