做运营那些无版权图片网站,韩国u17出线,绍兴seo优化,24小时最新在线视频免费观看例题1#xff1a;AcWing 291.蒙德里安的梦想 这题首先要将状态集合进行等效替代#xff1a;所有的合法方案等效于所有“先放横木块#xff0c;再放竖木块”的方案。所以我们只需要考虑摆放横木块的方案即可。那么很容易想到设计如下的DP#xff1a;fi,j表示已经填完前i-1列…例题1AcWing 291.蒙德里安的梦想这题首先要将状态集合进行等效替代所有的合法方案等效于所有“先放横木块再放竖木块”的方案。所以我们只需要考虑摆放横木块的方案即可。那么很容易想到设计如下的DPfi,j表示已经填完前i-1列且最后一列的状态为j突出为1不突出为0的方法总数那么显然fi,jfi-1,k其中k满足不与j上的任何一位重合且j与k合并后中间0的空隙长度为偶数这样才能放下竖木块。那么我们就需要判断ik是否为0且要预处理出每一个状态是否能放下竖木块然后检查状态j|k是否满足条件。代码如下#includeiostream#includevector#includecstringusingnamespacestd;constintN12,M1N;typedeflonglongll;vectorintstate[M];boolst[M];ll f[N][M];intmain(){intn,m;while(cinnm,n||m){for(inti0;i(1n);i){//预处理出每个状态的合法性intcnt0;boolflagtrue;for(intj0;jn;j){if(ij1){if(cnt1){flagfalse;break;}cnt0;}elsecnt;}if(cnt1)flagfalse;st[i]flag;}for(inti0;i(1n);i){state[i].clear();for(intj0;j(1n);j){if(!(ij)st[i|j]){state[i].push_back(j);}}}memset(f,0,sizeoff);f[0][0]1;for(inti1;im;i){for(intj0;j(1n);j){for(autok:state[j]){f[i][j]f[i-1][k];}}}coutf[m][0]endl;}return0;}例题2AcWing 292.炮兵阵地这题非常重要由这题引出了许多经典的状压DP问题。那么首先我们对于题意要正确理解任意一个炮兵部队不能部署在别的炮兵部队的攻击范围以内但是可以与别的炮兵部队攻击同一片区域这是我之前理解题意的一个很大的误区导致后面的引申题也做得不好。那么DP的设计方案就不再困难了仿照例题1的解法我们假设前i行已经摆好那么我们只要确定第i行与第i-1行的具体摆放情况就可以确定一个状态因为炮兵的攻击范围达到了2行所以第i-1行与第i-2行都会受到影响所以自身状态需要确定2行。那么我们可以初步想到DP的方法状态表示f[i][j][k]表示第i行已经摆好且第i行的炮兵摆放状态为j第i-1行的摆放状态为k且合法不会相互攻击到的可摆放的最大炮兵数。状态计算f[i][j][k]max(f[i][j][k],f[i-1][k][u]cnt[j]) 其中cnt[j]表示状态j中1的个数且这里面的jku可以共同组成一个合法图形那么接下来又是一个关键判断枚举的状态是否合法。1.首先对于状态自身进行考虑显然1个位置摆上炮兵后要隔上至少2个位置才能放炮兵2.再对枚举的三行状态ijk进行考虑由于炮兵的攻击范围是直接向上或向下两个单位所以ijk必须两两在同一个位置上一共最多有1个炮兵存在。用二进制表示就是ij0 jk 0 ki 0。3.由于地形的限制地形为山地的格子不能摆放炮兵。那么不妨设g[i]表示第i行中山地的分布情况用1表示山地0表示平原。那么用二进制表示就是g[i]j 0。最后是动规的边界与结果表示边界均定为0即可结果f[n2][0][0]当然这题直接这样做会MLE所以我们要加入滚动数组来优化空间这里不用一维数组的原因是方便修改否则需要修改枚举顺序。代码如下#includeiostream#includecstdio#includevectorusingnamespacestd;constintN105,M10,S1M;charc[N][M];intg[N],f[2][S][S],cnt[S];vectorintstate;intn,m;boolcheck(intx){for(inti0;im;i){if((xi1)((x(i1)1)||(x(i2)1)))returnfalse;}returntrue;}intcount(intx){intres0;while(x){if(x1)res;x1;}returnres;}intmain(){cinnm;for(inti0;in;i){scanf(%s,c[i]);}for(inti0;in;i){for(intj0;jm;j){if(c[i][j]H){g[i]1j;}}}for(inti0;i(1m);i){if(check(i)){state.push_back(i);cnt[i]count(i);}}for(inti0;in2;i){for(intj0;jstate.size();j){for(intk0;kstate.size();k){for(intu0;ustate.size();u){intastate[j],bstate[k],cstate[u];if((ab)||(bc)||(ac)||g[i]b)continue;f[i1][j][k]max(f[i1][j][k],f[(i-1)1][u][j]cnt[b]);}}}}coutf[(n1)1][0][0]endl;return0;}引出的问题AcWing 327.玉米田这题与上面的母题几乎一样只不过范围缩小了一些。那么这题就更加简单只要判断前一行与自己是否存在交集即可代码如下#includeiostream#includevectorusingnamespacestd;constintN15,M1N,mod1e8;intg[N],f[N][M];vectorintstate;intn,m;boolcheck(intx){for(inti0;im;i){if(xi1x(i1)1)returnfalse;}returntrue;}intmain(){cinnm;for(inti1;in;i){for(intj0;jm;j){intx;cinx;if(!x)g[i]1j;}}for(inti0;i(1m);i){if(check(i)){state.push_back(i);}}f[0][0]1;for(inti1;in1;i){for(intj0;jstate.size();j){intastate[j];if(g[i]a)continue;for(intk0;kstate.size();k){intbstate[k];if(ab)continue;f[i][a](f[i][a]f[i-1][b])%mod;}}}coutf[n1][0]endl;}练习题练习1洛谷P2622这题其实比较简单但是要注意到状态的更新并不是单调的所以需要利用类似bfs的形式采用队列来循环更新。#includebits/stdc.husingnamespacestd;constintN10,M105,INF0x3f3f3f3f;intf[1N],a[M][N];queueintq;intmain(){intn,m;cinnm;for(inti1;im;i){for(intj1;jn;j){cina[i][j];}}memset(f,0x3f,sizeoff);f[0]0;/*for(int i0;i(1n);i){ for(int j1;jm;j){ int statei; for(int k1;kn;k){ if(a[j][k]1 !((i(k-1))1)) state(1(k-1)); if(a[j][k]-1 (i(k-1))1) state-(1(k-1)); //注意到这里的状态不是单调变化的故应采用队列的方法循环更新 } couti statefuckf[i]endl; f[state]min(f[state],f[i]1); } } */q.push(0);while(q.size()){inttq.front();q.pop();if(t(1n)-1){coutf[t]endl;return0;}for(intj1;jm;j){intstatet;for(intk1;kn;k){if(a[j][k]1!((t(k-1))1))state(1(k-1));if(a[j][k]-1(t(k-1))1)state-(1(k-1));}if(f[state]f[t]1){f[state]min(f[state],f[t]1);q.push(state);}}}puts(-1);return0;}[SCOI2005]互不侵犯