題意：給定一個R*C的矩陣，選擇一個面積最小的子矩陣，使得其內(nèi)部‘.’的個數(shù)>=k。

解題思路：這道題如果時普通的枚舉，會要達(dá)到O(N^5)嚴(yán)重超時。這里可以采用高效的枚舉方法——尺取法。

首先還是用一個sum[i][j]記錄(1,1)到(i,j)所圍成的矩陣?yán)?#39;.'的個數(shù)。

接下來是比較關(guān)鍵的，如何采用尺取法。

可以兩層循環(huán)枚舉第i列到第j列，最內(nèi)層循環(huán)就是枚舉行了，在最內(nèi)層循環(huán)里，如果熟悉尺取法的話，會發(fā)現(xiàn)這是一個典型的尺取法模型。

這樣可以做到O(N^3)復(fù)雜度。

#include<iostream> #include<cstdio> #include<cstring> using namespace std;const int maxn = 305; const int inf = 0x7ffffff; int n,m,k,map[maxn][maxn],sum[maxn][maxn]; char str[maxn];int main() {while(scanf("%d%d%d",&n,&m,&k),n+m+k){for(int i = 1; i <= n; i++){scanf("%s",str+1);for(int j = 1; j <= m; j++){if(str[j] == '.')map[i][j] = 1;else map[i][j] = 0;sum[i][j] = sum[i][j-1] + map[i][j];}}for(int i = 2; i <= n; i++)for(int j = 1; j <= m; j++)sum[i][j] += sum[i-1][j];int ans = inf;for(int i = 1; i <= m; i++)for(int j = i; j <= m; j++){int p = 1;for(int t = 1; t <= n; t++){while(sum[t][j] - sum[t][i-1] - sum[p-1][j] + sum[p-1][i-1] >= k){ans = min(ans,(j - i + 1) * (t - p + 1));p++;}}}printf("%d\n",ans);}return 0; }

與50位技術(shù)專家面對面20年技術(shù)見證，附贈技術(shù)全景圖

總結(jié)

以上是生活随笔為你收集整理的hdu 1937(尺取法)的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。