山西网站建设软件,建立一个网站大约要多少钱,网站平台优化,手机版企业网站php正题 题目大意 n∗mn*mn∗m的矩阵#xff0c;有些阻挡#xff0c;求至少要多少个1∗21*21∗2或2∗12*12∗1的块铺在上面使得没用可以继续铺的地方。 解题思路
因为mmm很小#xff0c;明显状压。 用fi,j,kf_{i,j,k}fi,j,k表示第iii行#xff0c;上一行状态为jjj#xff…正题 题目大意
n∗mn*mn∗m的矩阵有些阻挡求至少要多少个1∗21*21∗2或2∗12*12∗1的块铺在上面使得没用可以继续铺的地方。 解题思路
因为mmm很小明显状压。 用fi,j,kf_{i,j,k}fi,j,k表示第iii行上一行状态为jjj当行状态为kkk。 枚举行数iii枚举第i−2i-2i−2和第i−1i-1i−1行的状态用dfsdfsdfs计算出这一行的状态然后在途中修改上一行的状态。然后转移。 codecodecode
#includecstdio
#includealgorithm
#includecstring
#includeiostream
#define N 75
#define MS 138
using namespace std;
int n,m,w[N],f[N][MS][MS],ans,ms,s,s1,s2,inf;
void change(int k,int x,int y,int z,int t)//dfs转移
{if(k!(x(1(k-1)))!(y(1(k-1)))) return;//还可以竖着if(k1!(y(1(k-1)))!(y(1(k-2)))) return;//还可以横着if(km){f[s][y][z]min(f[s][y][z],f[s-1][s1][s2]t);return;}change(k1,x,y,z,t);if(!(z(1k))!(y(1k)))//竖着摆change(k1,x,y|(1k),z|(1k),t1);if(km-1!(y(1k))!(y(1(k1))))//横着摆change(k2,x,y|(1k)|(1(k1)),z,t1);
}
int main()
{//freopen(cake.in,r,stdin);//freopen(cake.out,w,stdout);scanf(%d%d,n,m);for(int i1;in;i){for(int j0;jm;j){char c;cinc;w[i]1;if(c*) w[i]|1;}}memset(f,127/3,sizeof(f));inff[0][0][0];ms(1m)-1;f[0][ms][w[1]]0;for(int i1;in;i)for(int j0;jms;j)for(int k0;kms;k)if(f[i-1][j][k]inf){si;s1j;s2k;change(0,j,k,w[i1],0);}ans2147483647;for(int i0;ims;i)ansmin(ans,f[n][i][0]);printf(%d,ans);
}
