百度不收录网站关键词,网站备案要注意什么,wordpress备份恢复阿里云,广州建站网络公司什么是状压DP#xff1a; 动态规划的状态有时候比较恶心#xff0c;不容易表示出来#xff0c;需要用一些编码技术#xff0c;把状态压缩的用简单的方式表示出来。 典型方式#xff1a;当需要表示一个集合有哪些元素时#xff0c;往往利用2进制用一个整数表示。 动态规… 什么是状压DP 动态规划的状态有时候比较恶心不容易表示出来需要用一些编码技术把状态压缩的用简单的方式表示出来。 典型方式当需要表示一个集合有哪些元素时往往利用2进制用一个整数表示。 动态规划本来就很抽象状态的设定和状态的转移都不好把握而状态压缩的动态规划解决的就是那种状态很多不容易用一般的方法表示的动态规划问题这个就更加的难于把握了。难点在于以下几个方面状态怎么压缩压缩后怎么表示怎么转移是否具有最优子结构是否满足后效性涉及到一些位运算的操作虽然比较抽象但本质还是动态规划。找准动态规划几个方面的问题深刻理解动态规划的原理开动脑筋思考问题。这才是掌握动态规划的关键。 分析 运算名符号效果按位与如果两个相应的二进制位都为1则该位的结果值为1否则为0l按位或两个相应的二进制位中只要有一个为1该位的结果值为1^按位异或若参加运算的两个二进制位值相同则为0否则为1~取反~是一元运算符用来对一个二进制数按位取\反即将0变1将1变0左移用来将一个数的各二进制位全部左移N位右补0*右移将一个数的各二进制位右移N位移到右端 的低位被舍弃对于无符号数高位补0下面来看三道题目 例题一 [POJ3254]Corn Fields其实就是牛吃草 题目大意 一个矩阵里有很多格子每个格子有两种状态可以放牧和不可以放牧可以放牧用1表示否则用0表示在这块牧场放牛要求两个相邻的方格不能同时放牛不包括斜着的即牛与牛不能相邻。问有多少种放牛方案(一头牛都不放也是一种方案) 输入 1n121m12 输出 一个mod100000000的整数 样例输入 2 3 1 1 1 0 1 0 样例输出 9 分析 从题意我们可以知道牛与牛之间不能相邻我们可以很容易的想到可以一行一行的递推因为每只牛能不能放只与上一行和当前这一行有关。 所以dp中有一个维度是用来表示第几行的还有一个维度就是用来表示哪一行的状态的。 假设有m列则状态最多只有1《m-1种这是显然的。因为他每一列只有放和不放这两种决策。 那么怎么表示状态是个关键问题这就要用到状态压缩了用二进制来表示某个状态比如 0101代表的就是1、3列不放牛2、4列放牛。这样不仅省空间省代码还省时间。 要用位运算是必须的。 参考代码 #include cstdio
#include cstring
const int N 13;
const int M 1N;
const int mod 100000000;
int st[M],map[M]; ///分别存每一行的状态和给出地的状态
int dp[N][M]; //表示在第i行状态为j时候可以放牛的种数
bool judge1(int x) //判断二进制有没有相邻的1
{ return (x(x1));
}
bool judge2(int i,int x)
{ return (map[i]st[x]);
}
int main()
{ int n,m,x; while(~scanf(%d%d,n,m)) { memset(st,0,sizeof(st)); memset(map,0,sizeof(map)); memset(dp,0,sizeof(dp)); for(int i1;in;i) { for(int j1;jm;j){ scanf(%d,x); if(x0) map[i](1(j-1)); } } int k0; for(int i0;i(1m);i){ if(!judge1(i)) st[k]i; } for(int i0;ik;i) { if(!judge2(1,i)) dp[1][i]1; } for(int i2;in;i) { for(int j0;jk;j) { if(judge2(i,j)) //判断第i行 假如按状态j放牛的话行不行。 continue; for(int f0;fk;f) { if(judge2(i-1,f)) //剪枝 判断上一行与其状态是否满足 continue; if(!(st[j]st[f])) dp[i][j]dp[i-1][f]; } } } int ans0; for(int i0;ik;i){ ansdp[n][i]; ans%mod; } printf(%d\n,ans); } return 0;
} 例题二 [POJ3311]Hie With The Pie 题目大意 一个送外卖的人从0点出发要经过所有的地点然后再回到店里(就是0点)求最少花费的代价。 输入 1n10 输出 一个整数代表最小花费。 样例输入 3 0 1 10 10 1 0 1 2 10 1 0 10 10 2 10 0 0 样例输出 8 分析 怎么做我们可以先从暴力来分析分析。 搜索解法这种解法其实就是计算排列子集树的过程。从0点出发要求遍历123点后回到0点。以不同的顺序来依次遍历123点就会导出不同的路径0-1-2-3-00-1-3-2-0等等总共有3!6条路径需要考虑从中选出最短的那条就是所求。搜索解法的时间复杂度为 O(n!) 。 需要注意的是题目显然给的是个邻接矩阵并不代表各点之间的距离所以我们需要先Floyd求出各点的最短路 动归解法仔细观察搜索解法的过程其实是有很多重复计算的。比如从0点出发经过12345点后回到0点。那么0-1-2-(345三个点的排列)-0与0-2-1-(345三个点的排列)-0就存在重复计算345三点的排列-0路径集上的最短路径。只要我们能够将这些状态保存下来就能够降低一部分复杂度。下面就让我们用动归来求解这一问题。记dp(S,v)为走完了集合S后最后停留在v点的最小花费。 我们不难得出递推方程式为 dp[S][v] min(dp[S除去点v)][k] dis[k][v],dp[S][v]) 好吧o(╯□╰)o和floyd确实有那么二两相似。 参考代码 #includeiostream
#define INF 100000000
using namespace std;
int dis[12][12];
int dp[111][12];
int n,ans,_min;
int main()
{ //freopen(in.txt,r,stdin); while(scanf(%d,n) n) { for(int i 0;i n;i) for(int j 0;j n;j) scanf(%d,dis[i][j]); for(int k 0;k n;k) for(int i 0;i n;i) for(int j 0;j n;j) if(dis[i][k] dis[k][j] dis[i][j]) dis[i][j] dis[i][k] dis[k][j]; for(int S 0;S (1n)-1;S)//枚举所有状态用位运算表示 for(int i 1;i n;i) { if(S (1(i-1)))//状态S中已经过城市i { if(S (1(i-1))) dp[S][i] dis[0][i];//状态S只经过城市I最优解自然是从0出发到i的dis,这也是DP的边界 else//如果S有经过多个城市 { dp[S][i] INF; for(int j 1;j n;j) { if(S (1(j-1)) j ! i)//枚举不是城市I的其他城市 dp[S][i] min(dp[S^(1(i-1))][j] dis[j][i],dp[S][i]); //在没经过城市I的状态中寻找合适的中间点J使得距离更短和FLOYD一样 } } } } ans dp[(1n)-1][1] dis[1][0]; for(int i 2;i n;i) if(dp[(1n)-1][i] dis[i][0] ans) ans dp[(1n)-1][i] dis[i][0]; printf(%d/n,ans); } return 0;
} 例题三 [POJ1185]炮兵阵地 描述 司令部的将军们打算在N*M的网格地图上部署他们的炮兵部队。一个N*M的地图由N行M列组成地图的每一格可能是山地用”H” 表示也可能是平原用”P”表示如下图。在每一格平原地形上最多可以布置一支炮兵部队山地上不能够部署炮兵部队一支炮兵部队在地图上的攻击范围如图中黑色区域所示 如果在地图中的灰色所标识的平原上部署一支炮兵部队则图中的黑色的网格表示它能够攻击到的区域沿横向左右各两格沿纵向上下各两格。图上其它白色网格均攻击不到。从图上可见炮兵的攻击范围不受地形的影响。 现在将军们规划如何部署炮兵部队在防止误伤的前提下保证任何两支炮兵部队之间不能互相攻击即任何一支炮兵部队都不在其他支炮兵部队的攻击范围内在整个地图区域内最多能够摆放多少我军的炮兵部队。 输入 第一行输出数据测试组数X0~X~100 接下来每组测试数据的第一行包含两个由空格分割开的正整数分别表示N和M 接下来的N行每一行含有连续的M个字符(‘P’或者’H’)中间没有空格。按顺序表示地图中每一行的数据。0N 1000M 10。 输出 每组测试数据输出仅一行包含一个整数K表示最多能摆放的炮兵部队的数量。 样例输入 1 5 4 PHPP PPHH PPPP PHPP PHHP 样例输出 6 参考代码 #include cstdio
#include iostream
#include cstring
#include algorithm
using namespace std;
const int N 105;
int Map[N];
int dp[N][65][65]; //dp[i][j][k]表示放第i行时第i行为第j个状态第i-1行为第k个状态最多可以放多少个炮兵
int s[N], num[N];
int n, m, p; bool check(int x) { //判断本行的炮兵是否互相攻击 if(x (x 1)) return false; if(x (x 2)) return false; return true;
} int Count(int x)
{int i1, ans0; while(ix){if(xi) ans; i1; } return ans;
}
void Init()
{ p0; memset(s,0,sizeof(s)); memset(num,0,sizeof(num)); for(int i0;i(1m);i){if(check(i)){ s[p]i;num[p]Count(i); //计算状态为x时可以放多少个炮兵 } }
} int main() { char ch;scanf(%d%d, n, m);memset(dp, 0, sizeof(dp)); memset(Map, 0, sizeof(Map)); for(int i0;in;i){ for(int j0;jm;j){ cinch;if(ch H) Map[i](1(m-1-j));//P为0H为1 } } Init();//预处理出合法状态 for(int i 0; i p; i) //求第一行最多放多少 if(!(Map[0]s[i]))// 不在山上 dp[0][i][0]num[i]; for(int i 0; i p; i)//前两行最多放多少 {if(!(Map[1]s[i]))//不与第一行冲突 { for(int j0;jp;j){ if((!(s[i]s[j])))//一二行不冲突 { dp[1][i][j]max(dp[1][i][j],dp[0][j][0]num[i]);} } } } for(int r2;rn;r)//枚举行数 {for(int i0;ip;i)//当前行的状态 { if(!(s[i]Map[r]))//不在山上 { for(int j 0; j p; j) //上一行的状态 { if(!(s[j] Map[r-1]))//不在山上 { if(!(s[i] s[j]))//不与当前行冲突 { for(int k 0; k p; k)//上上一行的状态{ if(!(s[k] Map[r-2])) //不在山上 { if(!(s[j] s[k])) //不与上一冲突 { if(!(s[i] s[k]))//不与当前行冲突 { dp[r][i][j]max(dp[r][i][j],dp[r-1][j][k]num[i]); } } } } } } } } } } int ans 0; for(int i 0; i p; i){ for(int j 0; j p; j){ if(ansdp[n-1][i][j]) ansdp[n-1][i][j]; } } printf(%d\n, ans); return 0;
} 转载于:https://www.cnblogs.com/ibilllee/p/7651971.html
