文档章节

状压dp大总结1 [洛谷]

o
 osc_s28jz759
发布于 07/04 10:25
字数 3831
阅读 64
收藏 0

「深度学习福利」大神带你进阶工程师,立即查看>>>

前言

状态压缩是一种\(dp\)里的暴力,但是非常优秀,状态的转移,方程的转移和定义都是状压\(dp\)的难点,本人在次总结状压dp的几个题型和例题,便于自己以后理解分析状态和定义方式

状态压缩动态规划,就是我们俗称的状压\(dp\),是利用计算机二进制的性质来描述状态的一种\(dp\)方式。

很多棋盘问题都运用到了状压,同时,状压也很经常和BFS及\(dp\)连用。

状压\(dp\)其实就是将状态压缩成2进制来保存 其特征就是看起来有点像搜索,每个格子的状态只有\(1\)\(0\) ,是另一类非常典型的动态规划

NO.1 Corn Fields G

题目描述

农场主\(John\)新买了一块长方形的新牧场,这块牧场被划分成\(M\)\(N\)\((1 \le M \le 12; 1 \le N \le 12)\),每一格都是一块正方形的土地。\(John\)打算在牧场上的某几格里种上美味的草,供他的奶牛们享用。

遗憾的是,有些土地相当贫瘠,不能用来种草。并且,奶牛们喜欢独占一块草地的感觉,于是\(John\)不会选择两块相邻的土地,也就是说,没有哪两块草地有公共边。

\(John\)想知道,如果不考虑草地的总块数,那么,一共有多少种种植方案可供他选择?(当然,把新牧场完全荒废也是一种方案)

输入格式

第一行:两个整数\(M\)\(N\),用空格隔开。

\(2\)到第\(M+1\)行:每行包含\(N\)个用空格隔开的整数,描述了每块土地的状态。第\(i+1\)行描述了第\(i\)行的土地,所有整数均为\(0\)\(1\),是\(1\)的话,表示这块土地足够肥沃,\(0\)则表示这块土地不适合种草。

输出格式

一个整数,即牧场分配总方案数除以\(100,000,000\)的余数。

输入输出样例

输入 #1

2 3
1 1 1
0 1 0

输出 #1

9

分析

首先看到范围,\(M\)\(N\)的范围都极小,所以根据状压\(dp\)通性,显然要通过每行或者每一列的状态来进行转移。这个题比较灵性(恶心)的就是行为\(M\),颠覆认知……因为每个奶牛不能挨在一起,并且不种植也是一种方案,所以合法的状态肯定是要初始化一下的,即:

g[i]=(!(i<<1)&i&&!(i&(i>>1)))

这道题就是按每一行来进行状态转移,定义\(f[i][j]\)为第\(i\)行状态为\(j\)时的方案数,所以要从上一行转移而来,那么设上一行的状态为\(k\),所以就可以根据这个列出状态转移方程:

\[f[i][j] = f[i][j]+f[i-1][k] \]

最终的答案就是把最后一行每一个状态的答案加起来即可
具体的初始化见代码注释

代码

#include<bits/stdc++.h>
using namespace std;
const int maxn = 13;
const int mod = 100000000;
int n,m;
int jl[maxn][maxn];
int f[maxn][1<<maxn];
int ste[maxn],g[1<<maxn];
int main(){
	cin>>m>>n;
	for(int i=1;i<=m;++i){
		for(int j=1;j<=n;++j){
			cin>>jl[i][j];//记录矩阵
		}
	}
	for(int i=1;i<=m;++i){
		for(int j=1;j<=n;++j){
			ste[i] = (ste[i]<<1)+jl[i][j];//用二进制记录每一行的状态(有草的地方)
		}
	}
	f[0][0] = 1;
	int ms = 1<<n;//总状态
	for (int i = 0; i <ms; i++)
        g[i] = ((i&(i<<1))==0) && ((i&(i>>1))==0);//初始化出所有状态中的合法状态
	for(int i=1;i<=m;++i){//枚举每一行
		for(int j=0;j<ms;j++){//当前行状态
			if(g[j] && (j & ste[i]) == j){//该状态合法且当前放牛都是在有草的地方
				for(int k=0;k<ms;k++){//上一行状态
					if((k&j) == 0){//上一行与这一行不能有相同的状态,也就是牛不能相邻
						f[i][j] = (f[i][j]+f[i-1][k])%mod;
					}
				}
			}
		}
	}
	int ans = 0;
	for(int i=0;i<ms;++i){//累加每一个状态的方案
		ans =(ans+f[m][i])%mod;
	}
	cout<<ans%mod<<endl;//记得每一次都要取模
	return 0;
}

NO.2 No Change G

题目

约翰到商场购物,他的钱包里有\(K(1 \le K \le 16)\)个硬币,面值的范围是\(1..100,000,000\)

约翰想按顺序买 \(N\)个物品\((1 \le N \le 100,000)\),第\(i\)个物品需要花费\(c_i\)块钱,\((1 \le c_i \le 10,000)\)

在依次进行的购买\(N\)个物品的过程中,约翰可以随时停下来付款,每次付款只用一个硬币,支付购买的内容是从上一次支付后开始到现在的这些所有物品(前提是该硬币足以支付这些物品的费用)。不幸的是,商场的收银机坏了,如果约翰支付的硬币面值大于所需的费用,他不会得到任何找零。

请计算出在购买完\(N\)个物品后,约翰最多剩下多少钱。如果无法完成购买,输出\(-1\)

输入格式

  • Line \(1\): Two integers, \(K\) and \(N\).

  • Lines \(2..1+K\): Each line contains the amount of money of one of FJ's coins.

  • Lines \(2+K..1+N+K\): These \(N\) lines contain the costs of FJ's intended purchases.

输出格式

  • Line 1: The maximum amount of money FJ can end up with, or -1 if FJ cannot complete all of his purchases.

输入输出样例

输入 #1

3 6
12
15
10
6
3
3
2
3
7








输出 #1

12

说明/提示

FJ has \(3\) coins of values \(12, 15\), and \(10\). He must make purchases in sequence of value \(6, 3, 3, 2, 3\), and \(7\).

FJ spends his 10-unit coin on the first two purchases, then the 15-unit coin on the remaining purchases. This leaves him with the 12-unit coin.

分析

看到友好又有标志性的硬币数的范围,当然要从硬币使用作为状态来进行状压啦!所以我们的状态就定义为\(f[i]\)表示使用硬币状态为\(i\)的时候买的最大物品数,看题意大概就是买东西需要按顺序,所以我们维护一个前缀和来优化时间效率,并且记录一下所有硬币的价值总和,方便最后判断。与上一个题相似的是,也要把使用每个硬币的状态提前初始化一下:

\[g[i] = g[i-1]<<1; \]

表示的是只用了第\(i\)个硬币的状态。并且\(g[1]=1\)然后就可以愉快的状态转移了!状态转移就是用了状态为\(i的\)硬币时买的物品,与当前用了第\(j\)个硬币买的物品去最大值。状态转移方程比较特殊,所以一会在代码中解释。

状态转移完了就需要统计答案了,每次当前状态能买的最大物品为\(n\)时就开始统计。枚举硬币,如果当前状态用了该硬币,那么就让计数\(cnt\)加上当前硬币的价值,最后\(ans\)取最大的剩余价值。需要注意的是最后剩余可以为\(0\),所以\(ans\)应该初始化为\(-1\),如果小于\(0\),那么就是不可能的情况。

代码

#include<bits/stdc++.h>
using namespace std;
const int maxn = 1e6+10;
const int mm = 19;
int f[1<<mm];
int n,k;
int sum[maxn];
int g[maxn];
int tot,cnt,ans = -1;
int c[mm],a[maxn];
int main(){
	cin>>k>>n;
	for(int i=1;i<=k;++i){//输入硬币数并计算总价值
		cin>>c[i];
		tot += c[i];
	}
	for(int i=1;i<=n;++i){//输入每个物品价值并求出前缀和
		cin>>a[i];
		sum[i] = sum[i-1]+a[i];
	}
	g[1] = 1;
	for(int i=2;i<=k;++i){//初始化每个硬币使用的状态
		g[i] = g[i-1]<<1;
	}
	int ms = (1<<k)-1;
	for(int i=0;i<=ms;++i){//枚举所有状态
		for(int j=1;j<=k;++j){//枚举所有硬币
			if(i & g[j]){//当前状态用了该硬币就继续运行
				int te = f[i^g[j]];//te为没用该硬币时能卖的商品数。
				te = upper_bound(sum+1,sum+n+1,sum[te]+c[j])-sum;//二分求使用了第j个硬币后大于的第一个商品前缀和,就可以统计出能卖多少商品。
				f[i] = max(f[i],te - 1);//此时te-1为买了的商品数,取max更新
			}
		}
	}
	for(int i=0;i<=ms;++i){//再次枚举状态
		if(f[i] == n){//当前状态能够买完n个物品就继续进行
			cnt = 0;
			for(int j=1;j<=k;++j){
				if((i & g[j])){//当前状态用了第j个硬币就加上它的价值
					cnt += c[j];
				}
			}
			ans = max(ans,tot-cnt);//求出最大的剩余价值
		}
	}
	if(ans<0)cout<<-1<<"\n";//小于0就是不可能买完
	else cout<<ans<<endl;
}


NO.3 吃奶酪

题目描述

房间里放着 \(n\) 块奶酪。一只小老鼠要把它们都吃掉,问至少要跑多少距离?老鼠一开始在 \((0,0)\) 点处。

输入格式

第一行有一个整数,表示奶酪的数量 \(n\)

\(2\) 到第 \((n+1)\) 行,每行两个实数,第 \((i+1)\) 行的实数分别表示第 \(i\) 块奶酪的横纵坐标 \(x_i, y_i\)​。

输出格式

输出一行一个实数,表示要跑的最少距离,保留 \(2\) 位小数。

输入输出样例

输入 #1

4
1 1
1 -1
-1 1
-1 -1



输出 #1

7.41

说明/提示

数据规模与约定

对于全部的测试点,保证 \(1\le n\le 15\)\(|x_i|,|y_i| \le 200\),小数点后最多有 \(3\) 位数字。
提示

对于两个点 \((x_1,y_1)\)\((x_2, y_2)\),两点之间的距离公式为 \(\sqrt{(x_1-x_2)^2+(y_1-y_2)^2}\)​。

分析

再一次看到友好的奶酪数据范围,显然要从吃奶酪的状态入手转移,因为需要计算距离,所以我们需要把每个点之间的距离全部求出来,并且状态数组需要一维来存储上一次的位置,所以我们定义\(f[i][j]\)为吃奶酪状态\(i\)时位置为\(j\)的走的距离,也就是吃了奶酪\(j\),从上一个状态没吃\(j\)转移来,位置为\(k\)。所以状态转移方程就是:

\[dp[i][j] = min(dp[i][j],dp[i -(1<<(j-1))][k] + jl[k][j]); \]

\(jl\)就是距离……
而我们需要预处理一些东西,每个位置之间距离是一个,原点与每个位置之间距离也要预处理,然后就是只吃了一个奶酪的走的长度预处理,然后就可以愉快的状态转移了。最后不要忘了把每个位置吃完奶酪的走的距离都扫一边。

代码

#include<bits/stdc++.h>
using namespace std;
#define db double
const int maxn = 16;
double dp[1<<maxn][maxn];
int n;
db jl[maxn][maxn];
db jlx[maxn],jly[maxn];
db pow(db x){//求乘方
    return x*x;
}
db len(db xx,db yy,db x2,db y2){//求距离
    return sqrt(pow(xx-x2)+pow(yy-y2));
}


int main(){
    cin>>n;
    for(int i=1;i<=n;++i){
        cin>>jlx[i]>>jly[i];
        jl[0][i] = jl[i][0] = len(0,0,jlx[i],jly[i]);//原点到每个点的距离
    }
    for(int i=1;i<=n;++i){//每个位置之间的距离
        for(int j=1;j<=n;++j){
            jl[i][j] = len(jlx[i],jly[i],jlx[j],jly[j]);
        }
    }
    for(int i=1;i<(1<<n);++i){//初始化极大值
        for(int j=1;j<=n;++j){
            dp[i][j] = 999999.0;
        }
    }
    for(int i=1;i<=n;++i){//只吃了一个奶酪的距离
        dp[1<<(i-1)][i] = jl[0][i];
    }
    dp[0][0] = 0.0;
    for(int i=0;i<(1<<n);++i){//枚举状态
        for(int j=1;j<=n;++j){
            if((i & (1<<(j-1))) == 0)continue;  //没吃第j个就continue
            for(int k=1;k<=n;++k){
                if(k == j)continue;//上个位置和这个位置相同无意义,continue
                if((i & (1<<(k-1))) == 0)continue;//没吃第k个也没意义,continue
                dp[i][j] = min(dp[i][j],dp[i -  (1<<(j-1))][k] + jl[k][j]);//状态转移
            }
        }
    }
    db ans = 99999999.0;//一定是浮点数
    for(int i=1;i<=n;++i){//从头到尾扫一边
        ans = min(ans,dp[(1<<n)-1][i]);
    }
    printf("%.2lf",ans);
}

NO.4 中国象棋

题目描述

这次小可可想解决的难题和中国象棋有关,在一个\(N\)\(M\)列的棋盘上,让你放若干个炮(可以是\(0\)个),使得没有一个炮可以攻击到另一个炮,请问有多少种放置方法。大家肯定很清楚,在中国象棋中炮的行走方式是:一个炮攻击到另一个炮,当且仅当它们在同一行或同一列中,且它们之间恰好 有一个棋子。你也来和小可可一起锻炼一下思维吧!

输入格式

一行包含两个整数\(N\)\(M\),之间由一个空格隔开。

输出格式

总共的方案数,由于该值可能很大,只需给出方案数模\(9999973\)的结果。

输入输出样例

输入 #1

1 3

输出 #1

7

说明/提示

样例说明

除了\(3\)个格子里都塞满了炮以外,其它方案都是可行的,所以一共有\(2\times 2\times 2-1=7\)种方案。

数据范围

\(100\%\)的数据中\(N\)\(M\)均不超过\(100\)

\(50\%\)的数据中\(N\)\(M\)至少有一个数不超过\(8\)

\(30\%\)的数据中\(N\)\(M\)均不超过\(6\)

分析

其实这个题像极了线性dp,但是思想跟状压有一丢丢相似
想必大家都知道象棋规则吧,不知道的可以去问问度娘,按照象棋的规则,一行或者一列里最多有两个炮,所以就可以根据这个来转移了。
而且每一行也最多放两个,所以就可以一一枚举进行转移,方程过多,在这里就不列举出来了,具体见代码注释吧。
\(f[i][j][k]\)表示第\(i\)


代码

#include<bits/stdc++.h>
using namespace std;
const int maxn = 101;
const int Mod = 9999973;
int n,m;
long long f[maxn][maxn][maxn];
int Pow(int num){
	return num*(num-1)/2;
}
int main(){
	ios::sync_with_stdio(false);//cin/cout优化,加不加无所谓……
	cin.tie(0);
	cin>>n>>m;
	f[0][0][0] = 1;
	for(int i=0;i<n;++i){//枚举行
		for(int j=0;j<=m;++j){//枚举有一个棋子的列数
			for(int k=0;j+k<=m;++k){//两个棋子的列数
				if(f[i][j][k]){//上一次状态不为0才转移
					f[i+1][j][k]=(f[i+1][j][k]+f[i][j][k])%Mod;//不放棋子
					if(m-k-j>=1)f[i+1][j+1][k]=(f[i+1][j+1][k]+f[i][j][k]*(m-k-j))%Mod;//在没放棋子的列放一个
					if(j>=1)f[i+1][j-1][k+1]=(f[i+1][j-1][k+1]+f[i][j][k]*j)%Mod;//在放了一个棋子的列放一个
					if(m-k-j>=2)f[i+1][j+2][k]=(f[i+1][j+2][k]+f[i][j][k]*Pow(m-k-j))%Mod;//在没放棋子的列分别放两个
					if(m-k-j>=1 && j>=1)f[i+1][j][k+1]=(f[i+1][j][k+1]+f[i][j][k]*(m-k-j)*j)%Mod;//放了一个棋子和没放棋子的列各放一个
					if(j>=2)f[i+1][j-2][k+2]=(f[i+1][j-2][k+2]+f[i][j][k]*Pow(j))%Mod;//在放了一个棋子的列各放一个
				}
			}
		}
	}
	long long ans= 0;
	for(int i=0;i<=m;++i){
		for(int j=0;i+j<=m;++j){//统计答案
			ans=(ans+f[n][i][j])%Mod;
		}
	
	}
	cout<<ans<<"\n";
}/*最后搞个总结,每次从上个状态转移而来,如果放了一个棋子,一定要乘以剩下能放棋子列的个数,放两个当然是要乘以组合数了,这样才能求出方案数*/
o
粉丝 0
博文 64
码字总数 0
作品 0
私信 提问
加载中
请先登录后再评论。
我的架构演化笔记 功能1: 基本的用户注册

“咚咚”,一阵急促的敲门声, 我从睡梦中惊醒,我靠,这才几点,谁这么早, 开门一看,原来我的小表弟放暑假了,来南京玩,顺便说跟我后面学习一个网站是怎么做出来的。 于是有了下面的一段...

强子哥哥
2014/05/31
976
3
DephtInition

使用微软Kinect平台进行3D扫描是一种常见方法,如今计算机工程师吉安卡洛已经找到了一种新的方式:使用对焦堆叠。这个概念被称为焦点深度,通常使 用在显微镜中。吉安卡洛将其进行了简化,设...

troika
2013/06/30
2K
1
设计模式的误区,Java程序员对设计模式的诋毁及滥用

首先,设计模式是一种程序设计的方法,指的是某一领域/类型的程序的设计方法。 所有的设计模式都是在前人/以往软件的基础上总结的,这一点需要非常注意。 Java程序员对设计模式第一个诋毁的就...

clonne
2012/07/07
2.3K
35
Spark数据挖掘-深入GraphX(1)

Spark数据挖掘-深入GraphX(1) 1 网络数据集 当图被用来描述系统中的组件之间的交互关系的时候,图可以被用来表示任何系统。图原理提供了通用的语言和一系列工具来表示和分析复杂的系统。简单...

clebeg
2015/11/26
970
2
AS打包aar文件的方法及使用总结

一.编写aar架包的方式 在app的build.gradle中配置 apply plugin: 'com.android.library' 删除 applicationId "com.***" 二.关于打包 打包aar架包的方法 ./gradlew assemble 会在文件build/o......

海阔天空玩世不恭
2015/12/21
5.7K
0

没有更多内容

加载失败,请刷新页面

加载更多

创建具有列表理解的字典 - Create a dictionary with list comprehension

问题: I like the Python list comprehension syntax. 我喜欢Python列表理解语法。 Can it be used to create dictionaries too? 它也可以用来创建字典吗? For example, by iterating over......

技术盛宴
57分钟前
15
0
从JS数组中删除重复的值[duplicate] - Remove duplicate values from JS array [duplicate]

问题: This question already has answers here : 这个问题已经在这里有了答案 : Get all unique values in a JavaScript array (remove duplicates) (79 answers) 获取JavaScript数组中的......

法国红酒甜
今天
11
0
如何使用AngularJS在浏览器的控制台中访问$ scope变量?

问题: I would like to access my $scope variable in Chrome's JavaScript console. 我想在Chrome的JavaScript控制台中访问$scope变量。 How do I do that? 我怎么做? I can neither see ......

fyin1314
今天
18
0
ImageMagick - 添加水印

背景 最近制作思维导图想添加自己的水印,网上很多例子都是使用ImageMagick来完成。但是不少代码在本地并不可行。经过一番试验,找到两个方法。 方法一 代码 stackoverflow方法改良: conver...

wffger
今天
11
0
OSChina 周四乱弹 —— 到底是怎样的饕餮盛宴在等待着我!

Osc乱弹歌单(2020)请戳(这里) 【今日歌曲】 小小编辑推荐 :《你 能 來 保 護 我 的 世 界 嘛》- 歪门 《你 能 來 保 護 我 的 世 界 嘛》- 歪门 手机党少年们想听歌,请使劲儿戳(这里)...

小小编辑
今天
77
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部