建材网站制作,免费虚拟主机代理,有限责任公司设立条件,安徽省住房城乡建设厅门户网站目录 今日知识点#xff1a;
把状态压缩成j,dp每行i的布置状态#xff0c;从i-1和i-2行进行不断转移
把状态压缩成j,dp每行i的布置状态#xff0c;从i-1行进行状态匹配#xff0c;然后枚举国王数转移 POJ1185#xff1a;炮兵阵地
思路#xff1a;
题目#xff1a;互… 目录 今日知识点
把状态压缩成j,dp每行i的布置状态从i-1和i-2行进行不断转移
把状态压缩成j,dp每行i的布置状态从i-1行进行状态匹配然后枚举国王数转移 POJ1185炮兵阵地
思路
题目互不侵犯
思路 POJ1185炮兵阵地
在N*M(N100,M10)的地图上布置炮兵H格子为山地不能布置P格子为平原可以布置。炮兵的攻击范围是沿横向左右各两格沿纵向上下个两格子 炮兵之间不能误伤。问在整个地图中最多能拜访多少个炮兵 5 4 PHPP PPHH PPPP PHPP PHHP 思路
还是那么句话每个格子都有2种状态如果搜索就要把所有结果都跑出来所以只能使用状压dp 。
而且方程的转移和上一行的状态有关但是状态又太多了故要状态压缩。
首先要对行进行状态压缩(对列的话太大了枚举2^100还不如不压缩呢)我们每次确定行的状态都需要考虑1.横向方案 2.横向方案是否和地图匹配 3.是否和i-1行i-2行冲突设置dp[i][j][k]表示第i行为第j状态第i-1行为第k状态时 对应的前i行放置的最大炮兵数。转移方程dp[i][j][k]max(dp[i][j][k],dp[i-1][k][t]num[j]);num是对应状态的炮兵个数
j是第i行的方案k是第i-1行的方案t是i-2行的方案存每行的可能状态左右相邻1个间隔和2个间隔都不能炮兵就是可能的横向方案存图(1,1)开始存。0表示平原1表示山地那么在放置的时候不能出现同1(在山地放炮兵)所以xy0是合法的保证合法的是0就行了是否冲突第i行和第i-1行第i-2行 不能出现有一列同1(两行都放炮兵)所以xy0是合法的 【注意】外面每行i循环一次其次里面是第i行的每个状态j循环一次(找到合适的j)然后是第i-1行的每个状态k循环一次(供第i行找到合适的k) 接着是第i-2行的每个状态t循环一次(供第i-1行找到合适的t)
#include bits/stdc.h
using namespace std;
int n,m,top;
char mp[110][20];
int num[70];//num存放状态对应的炮兵个数
int ok[70],cur[70];//ok表示横向可能的方案cur是我们存的地图行
int dp[110][70][70];bool check(int x){if(x(x1))return 0;//相邻1间隔是否合法if(x(x2))return 0;//相邻2间隔是否合法return 1;
}void init(){//统计所有的可能合法状态最多60种top0;for(int i0;i(1m);i){//不能取等不能取等if(check(i))ok[top]i;}
}int count(int x){//统计x二进制中1的个数int cnt0;while(x){if(x1)cnt;xx1;}
// while(x){//这个更快
// cnt;
// x(x-1);
// } return cnt;
}int solve(){int ans0;memset(dp,-1,sizeof(dp));for(int j0;jtop;j){//初始化第一行的状态num[j]count(ok[j]);//记录每个正确状态的炮兵个数if(!(ok[j]cur[1])){//和地图匹配dp[1][j][0]num[j];//第一行状态为j上一行状态为0知道为啥从(1,1)开始初始化了把ansmax(ans,dp[1][j][0]);}}for(int i2;in;i){//处理每一行for(int j0;jtop;j){//遍历第i行的可能方案if(ok[j]cur[i])continue;//是否和地图匹配for(int k0;ktop;k){//遍历第i-1行的可能方案if(ok[j]ok[k])continue;//此行和上一行是否匹配不用再判断和地图是否匹配不匹配dp是-1不影响的for(int t0;ttop;t){//遍历上二行可能方案if(ok[j]ok[t])continue;//此行和上二行是否匹配dp[i][j][k]max(dp[i][j][k],dp[i-1][k][t]num[j]);}if(in)ansmax(ans,dp[i][j][k]);//不要放在外面套3个for取max}}}return ans;
}
int main(){while(cinnm){init();for(int i1;in;i){scanf(%s,mp[i]1);//加1是为了从1下标开始存}for(int i1;in;i){cur[i]0;for(int j1;jm;j){if(mp[i][j]H)//同样的不能放的地方存1cur[i](1(m-j));}}coutsolve();}
}题目互不侵犯 思路
可以看到和炮兵阵地题非常像跑不了是状压dp。
还是那句话每个方格都有两种状态搜索的话必然是要全部搜索一下放弃吧况且不谈超时你真的把本道题的dfs其实也够呛的。
设置dp[i][j][k]表示第i行为j状态时已经放了k个国王对应的方案数。
转移方程dp[i][j][k]dp[i-1][i-1行所有的合法状态][k-对应状态的国王数]
然后就是对状态的处理
行内状态我们要保证相与出0合法非0不合法。那么对s行
有(((s1)s0)((s1)s)0)算合法
等价于这个写法(((s1)|(s1))s)0。 千万别少写红色括号 行间状态((s2s10)((s21)s10)((s21)s1)0)才算合法
等价于(((s2|(s21)|(s21))s1)0。
循环方式首先是每行然后选择该行状态然后是上行状态判断两行状态是否匹配如果匹配就枚举国王数最后转移方程
#include bits/stdc.h
using namespace std;
int num,n,k;//ok存正确的行状态cnt存状态对应的国王数
long long dp[10][100][2000],cnt[2000],ok[2000];
int main(){cinnk;for(int s0;s(1n);s){//遍历出所有的正确状态iint tot0,tmps;while(tmp){if(tmp1)tot;tmp1;}cnt[s]tot;//存每个状态的国王数if((((s1)|(s1))s)0) ok[num]s;}dp[0][0][0]1;for(int i1;in;i){//从第一行开始转移for(int ss11;ss1num;ss1){int s1ok[ss1];//选择第一行的状态for(int ss21;ss2num;ss2){int s2ok[ss2];//选择上一行的状态if(((s2|(s21)|(s21))s1)0){//如果这两行状态合法for(int j0;jk;j){//对国王数进行枚举转移if(j-cnt[s1]0)dp[i][j][s1]dp[i-1][j-cnt[s1]][s2];}}}}}long long ans0;for(int i1;inum;i)ansdp[n][k][ok[i]];coutans;
}
