什么是网站站点建设介绍,环保局网站建设 自查报告,怀化seo公司,深圳宝安区住房和建设局网站前言
水解警告#xff0c;数据水勉强卡过的 正题 题目大意 n∗mn*mn∗m的网格里面有些格子被禁止#xff0c;现在求选取若干个不相邻的格子的方案数。 1≤n≤120,1≤m≤211\leq n\leq 120,1\leq m\leq 211≤n≤120,1≤m≤21 解题思路
听说是插头dpdpdp然后想了一下觉得比插…前言
水解警告数据水勉强卡过的 正题 题目大意
n∗mn*mn∗m的网格里面有些格子被禁止现在求选取若干个不相邻的格子的方案数。
1≤n≤120,1≤m≤211\leq n\leq 120,1\leq m\leq 211≤n≤120,1≤m≤21 解题思路
听说是插头dpdpdp然后想了一下觉得比插头dpdpdp的模板简单多了。
如果这个轮廓线外侧有玉米就相当于有一个插头然后发现右插头一定和刚刚那个格子的下插头相等所以只需要存储下插头的状态就好了。
然后暴力搜出所有合法状态注意因为轮廓线下凸的地方可以有两个相邻的111所以只有一个位置有两个相邻格子的状态也算合法状态只有129267129267129267个。
然后因为状态大小的上限2m2^m2m所以可以直接暴力用一个数组来记录状态不用挂表了。
然后转移也很好写。
所以写起来很舒服但是这样不吸氧跑的很慢。时间复杂度换代码复杂度
QuantAsk在玉米田吸氧这是他的代码运行时间发生的变化
但是其实看了一下正解的写法还有一个优化就是记下第一个相邻111的插头位置然后挂表然后对于每个位置只考虑在轮廓线下凸位置有相邻111的状态好像会快很多状态也少很多。 code
#includecstdio
#includecstring
#includealgorithm
#define adt(x,y) ((xyP)?xy-P:xy)
using namespace std;
const int P1e8;
int n,m,o,cnt,p,ans,v[200],t[2],mark[2][129268],s[2][129268],f[2][129268],S[121];
void Add(int z,int v){int xS[z];if(mark[o][x]!p){f[o][x]v;s[o][t[o]]z;mark[o][x]p;return;}f[o][x]adt(f[o][x],v);return;
}
int main()
{freopen(cowfood.in,r,stdin);freopen(cowfood.out,w,stdout);scanf(%d%d,n,m);for(int i0;in;i){for(int j0,x;jm;j)scanf(%d,x),v[i]|((!x)j);}p;for(int i0;i1m;i){int flag0;for(int j1;jm;j)if(((ij)1)((ij-1)1))flag;if(flag2){cnt,S[i]cnt;if(flag1!(iv[0])){f[o][cnt]1;mark[o][cnt]p;s[o][t[o]]i;}}}int z,w;for(int i1;in;i)for(int j0;jm;j){p;o!o;t[o]0;for(register int k1;kt[!o];k){zs[!o][k];wf[!o][S[z]];if((zj)1)Add(z^(1j),w);else if((j0((zj-1)1))||((v[i]j)1))Add(z,w);else Add(z,w),Add(z|(1j),w);}}for(int k1;kt[o];k)ansadt(ans,f[o][S[s[o][k]]]);printf(%d\n,ans);
}
