状压dp经典问题及代码

状压dp

tsp问题

需积分: 50 179 浏览量更新于2023-05-25 收藏 242KB PDF 举报

身份认证购VIP最低享 7 折!

领优惠券(最高得80元）

资源详情

资源推荐

1 / 18

动态规划本来就很抽象，状态的设定和状态的转移都不好把握，而状态压缩

的动态规划解决的就是那种状态很多，不容易用一般的方法表示的动态规划

问题，这个就更加的难于把握了。

难点在于以下几个方面：状态怎么压缩？压缩后怎么表示？怎么转移？是否

具有最优子结构？是否满足后效性？涉及到一些位运算的操作，虽然比较抽

象，但本质还是动态规划。

找准动态规划几个方面的问题，深刻理解动态规划的原理，开动脑筋思考问

题。这才是掌握动态规划的关键。

动态规划最关键的要处理的问题就是位运算的操作，容易出错，状态的设计

也直接决定了程序的效率，或者代码长短。

状态转移方程一定要仔细推敲，不可一带而过，要思考为什么这么做，掌握

一个套路，遇见这类问题能快速的识别出问题的本质，找出状态转移方程和

DP 的边界条件。

下面是一些关于状态压缩 DP 的题目，大都不难。状压 DP 的东西还有很多，

还会接着总结。

【POJ3254】Corn Fields

【题目大意】一个矩阵里有很多格子，每个格子有两种状态，可以放牧和不

可以放牧，可以放牧用 1 表示，否则用 0 表示，在这块牧场放牛，要求两个

相邻的方格不能同时放牛，即牛与牛不能相邻。问有多少种放牛方案(一头牛

都不放也是一种方案)

【解析】根据题意，把每一行的状态用二进制的数表示，0 代表不在这块放牛，

1 表示在这一块放牛。首先很容易看到，每一行的状态要符合牧场的硬件条件，

即牛必须放在能放牧的方格上。这样就能排除一些状态。另外，牛与牛之间

不能相邻，这样就要求每一行中不能存在两个相邻的 1，这样也能排除很多状

态。然后就是根据上一行的状态转移到当前行的状态的问题了。必须符合不

能有两个 1 在同一列（两只牛也不能竖着相邻）的条件。这样也能去掉一些

状态。然后，上一行的所有符合条件的状态的总的方案数就是当前行该状态

的方案数。

【状态表示】dp[state][i]：在状态为 state 时，到第 i 行符合条件的可以放牛

的方案数

【状态转移方程】dp[state][i] =Sigma dp[state'][i-1] （state'为符合条件的

所有状态）

【DP 边界条件】首行放牛的方案数 dp[state][1] =1(state 符合条件) OR 0

(state 不符合条件)

【代码】

#include <cstdio>

#include <cstring>

using namespace std;

#define mod 100000000

int M,N,top = 0;

int state[600],num[110];

int dp[20][600];

int cur[20];

inline bool ok(int x){

if(x&x<<1)return 0;

3 / 18

}

for(int i = 2; i <= M; ++i){

for(int k = 1; k <= top; ++k){

if(!fit(state[k],i))continue;

for(int j = 1; j <= top ;++j){

if(!fit(state[j],i-1))continue;

if(state[k]&state[j])continue;

dp[i][k] = (dp[i][k] +dp[i-1][j])%mod;

}

int ans = 0;

for(int i = 1; i <= top; ++i){

ans = (ans + dp[M][i])%mod;

}

printf("%d\n",ans);

}

【POJ1185】炮兵阵地--经典状压 DP

【题目大意】类似于上面一道题，一个方格组成的矩阵，每个方格可以放大

炮用 0 表示，不可以放大炮用 1 表示（原题用字母），让放最多的大炮，大

炮与大炮间不会互相攻击。

【解析】可以发现，对于每一行放大炮的状态，只与它上面一行和上上一行

的状态有关，每一行用状态压缩的表示方法，0 表示不放大炮，1 表示放大炮，

同样的，先要满足硬件条件，即有的地方不能放大炮，然后就是每一行中

不能有两个 1 的距离小于 2（保证横着不互相攻击），这些要预先处理一下。

然后就是状态表示和转移的问题了，因为是和前两行的状态有关，所以要

开个三维的数组来表示状态，当前行的状态可由前两行的状态转移而来。

即如果当前行的状态符合前两行的约束条件（不和前两行的大炮互相攻

击），则当前行的最大值就是上一个状态的值加上当前状态中 1 的个数（当

前行放大炮的个数）

【状态表示】dp[i][j][k] 表示第 i 行状态为 k，第 i-1 状态为 j 时的最大炮兵个

数。

【状态转移方程】dp[i][k][t] =max(dp[i][k][t],dp[i-1][j][k]+num[t]); num[t]

为 t 状态中 1 的个数

【DP 边界条件】dp[1][1][i] =num[i] 状态 i 能够满足第一行的硬件条件（注

意：这里的 i 指的是第 i 个状态，不是一个二进制数，开一个数组保存二进制

状态）

【代码】

#include <cstdio>

剩余17页未读，继续阅读

Star77777

粉丝: 99
资源: 5

会员权益专享

状压dp经典问题及代码

状压DP_C++_算法_状压_状态压缩DP_状压DP_

dp状态压缩

经典树型DP状态压缩DP入门

状压DP一般分为哪几类

蓝桥杯国赛 矩阵计数（python-状压DP）

tsp问题DP算法的伪代码

用Java写段dp解决斐波那契问题的代码

dp算法 能量管理 代码

帮我写一个dp接口的verilog代码

profibus dp 主站 代码

帮我写个dp接口的Verilog代码

rk3399平台dp驱动代码

profibus dp代码实现

C++ DP背包问题

acm0基础动态规划

class Solution { public: int climbStairs(int n) { if (n <= 1) return n; int dp[3]; dp[1] = 1; dp[2] = 2; for (int i = 3; i <= n; i++) { int sum = dp[1] + dp[2]; dp[1] = dp[2]; dp[2] = sum; } return dp[2]; } };请将这段代码改为可编译的代码

dp凑数不重复c++代码

四位数字数码管的数字钟的dp代码

会员权益专享

最新资源

蓝桥杯国赛矩阵计数（python-状压DP）

dp算法能量管理代码

profibus dp 主站代码