題目請戳這里

題目大意:給一個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;}elseh[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

總結

以上是生活随笔為你收集整理的poj2032Square Carpets(IDA* + dancing links)的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。