题目请戳这里
题目大意:给一个H行W列的01矩阵,求最少用多少个正方形框住所有的1.
题目分析:又是一个红果果的重复覆盖模型.DLX搞之!
枚举矩阵所有的子正方形,全1的话建图.判断全1的时候,用了一个递推,dp[i][j][w][h]表示左上角(i,j)的位置开始长h宽w的矩形中1的个数,这样后面可以迅速判断某个正方形是否全1.
不过此题直接搜一直TLE,然后改成迭代加深就比较愉快啦
详情请见代码:
#include <iostream> #include<cstdio> #include<cstring> #include<algorithm> using namespace std; const int N = 11; const int M = 50005; int dp[N][N][N][N]; int n,m,num,ans; int mp[N][N]; bool vis[105]; int s[M],h[M],col[M],u[M],d[M],l[M],r[M]; void init() { memset(h,0,sizeof(h)); memset(s,0,sizeof(s)); int i,c; c = m * n; for(i = 0;i <= c;i ++) { u[i] = d[i] = i; l[i] = (i + c)%(c + 1); r[i] = (i + 1)%(c + 1); } num = c + 1; } void ins(int i,int j) { if(h[i]) { r[num] = h[i]; l[num] = l[h[i]]; r[l[num]] = l[r[num]] = num; } else h[i] = l[num] = r[num] = num; s[j] ++; u[num] = u[j]; d[num] = j; d[u[num]] = num; u[j] = num; col[num] = j; num ++; } void del(int c) { for(int i = u[c];i != c;i = u[i]) l[r[i]] = l[i],r[l[i]] = r[i]; } void resume(int c) { for(int i = d[c];i != c;i = d[i]) l[r[i]] = r[l[i]] = i; } int A() { int i,j,k,ret; ret = 0; memset(vis,false,sizeof(vis)); for(i = r[0];i;i = r[i]) { if(vis[i] == false) { ret ++; vis[i] = true; for(j = d[i];j != i;j = d[j]) for(k = r[j];k != j;k = r[k]) vis[col[k]] = true; } } return ret; } bool dfs(int k,int lim) { if(k + A() > lim) return false; if(!r[0]) { // ans = min(ans,k); return true; } int i,j,c,mn = M; for(i = r[0];i;i = r[i]) { if(s[i] < mn) { mn = s[i]; c = i; } } for(i = d[c];i != c;i = d[i]) { del(i); for(j = l[i];j != i;j = l[j]) del(j); if(dfs(k + 1,lim)) return true; for(j = r[i];j != i;j = r[j]) resume(j); resume(i); } return false; } bool canfuck(int x,int y,int z) { return dp[x][y][z][z] == z * z; int i,j; for(i = x;i <= x + z - 1;i ++) for(j = y;j <= y + z - 1;j ++) if(mp[i][j] == 0) return false; return true; } void fuckba(int x,int y,int z,int id) { int i,j; for(i = x;i <= x + z - 1;i ++) for(j = y;j <= y + z - 1;j ++) ins(id,(i - 1) * m + j); } void build() { int i,j,k; memset(dp,0,sizeof(dp)); for(i = 1;i <= n;i ++) for(j = 1;j <= m;j ++) scanf("%d",&mp[i][j]),dp[i][j][1][1] = mp[i][j]; for(int ii = 1;ii <= n;ii ++) for(int jj = 1;jj <= m;jj ++) { for(i = 1;i + ii <= n + 1;i ++) { for(j = 1;j + jj <= 1 + m;j ++) { dp[i][j][ii][jj] = dp[i][j][ii - 1][jj - 1] + dp[i + ii - 1][j][1][jj - 1] + dp[i][j + jj - 1][ii - 1][1] + dp[i + ii - 1][j + jj - 1][1][1]; } } } init(); int rownum = 1; for(k = 1;k <= min(n,m);k ++)//枚举边长 { for(i = 1;i <= n - k + 1;i ++) { for(j = 1;j <= m - k + 1;j ++) { if(canfuck(i,j,k)) fuckba(i,j,k,rownum); rownum ++; } } } for(i = 1;i <= n * m;i ++) if(s[i] == 0) l[r[i]] = l[i],r[l[i]] = r[i]; } void fuck() { // ans = M;TLE.... // dfs(0); // printf("%d\n",ans); ans = 0; while(!dfs(0,ans ++)); printf("%d\n",ans - 1); } int main() { while(scanf("%d%d",&m,&n),(m + n)) { build(); fuck(); } return 0; }
转载于:https://www.cnblogs.com/riasky/p/3481865.html
相关资源：各显卡算力对照表！