題目:
做了兩個多小時,腦洞大開,給了一個01矩陣,求以a,b,為左上角,c,d為右下角的矩陣内有多少包含部分全為0的子矩陣
對于這道題目,一開始就想到了DP遞推,感覺而已,雖然準,可是做不出啊,想好了遞推式子可是細節部分沒辦法去處理。看了CF上的題解,頓時腦洞大開,這個做法真的是太厲害了,這方法代碼簡潔明了,同時也提醒到了我,在方程假設出來後,對于轉移的細節處理,
其實一開始我想到過這個遞推式子
dp[i][j][k][l] += dp[i][j][k - 1][l] + dp[i][j][k][l - 1] - dp[i][j][k - 1][l - 1];對于這個式子,就還差一個,那就是包含(c,d)也就是右下角的矩陣數目,這個當時無法去求,現在覺得這方法真的太巧妙了,可以先開一個二維數組last[i][j],代表目前(i,j)這個點距離它同一行左邊距離它最近的 一個1的距離,如果它左邊沒有1,那麼就是距離左邊第一列 也就是矩陣左邊界的距離,
一開始設定一個值 l - j + 1,也就是左上角的點與右下角的點的 列數之間的距離,然後開始枚舉從右下角到左上角的 行數 中的last[kk][l]的值,(i<=kk<=k),取兩個之間曉得的那個加上,為什麼呢
比如說:
000
000,這個子矩陣一開始l - j + 1 = 3,然後枚舉行數,發現最終答案是6,數一數包含右下角的點的 矩陣個數确實是六,因為要包含右下角是以多一行其實就是個數多了一倍而已
再舉個例子:
010
000,一開始l - j + 1 = 3,開始枚舉行數,最終答案是4,為什麼呢,因為要包含右下角的點,是以當你一旦遇到1的時候,那麼其實從這個1所在位置開始的 左邊上邊部分都可以去掉了,隻有這個1以及1上邊的右邊部分可以用了, 這方法真神!
int n,m,q;
int mp[40 + 5][40 + 5];
int dp[40 + 5][40 + 5][40 + 5][40 + 5];
int last[40 + 5][40 + 5];//與左邊最近的一個1的距離,
void init() {
memset(dp,0,sizeof(dp));
memset(last,0,sizeof(last));
}
bool input() {
while(cin>>n>>m>>q) {
for(int i=1;i<=n;i++) {
string s;
cin>>s;
for(int j=1;j<=m;j++) {
mp[i][j] = s[j - 1] - '0';
}
}
return false;
}
return true;
}
void slove() {
for(int i=1;i<=n;i++) {
for(int j=1;j<=m;j++) {
if(mp[i][j]){last[i][j] = 0;continue;}
last[i][j] = last[i][j - 1] + (mp[i][j] == 0);
}
}
for(int i=1;i<=n;i++) {
for(int j=1;j<=m;j++) {
for(int k=i;k<=n;k++) {
for(int l=j;l<=m;l++) {
int tmp = l - j + 1;
//int tt = 0;
for(int kk = k;kk >= i;kk--) {
tmp = min(tmp,last[kk][l]);
dp[i][j][k][l] += tmp;
//tt += tmp;
//cout<<tt<<"****"<<endl;
}
dp[i][j][k][l] += dp[i][j][k - 1][l] + dp[i][j][k][l - 1] - dp[i][j][k - 1][l - 1];
}
}
}
}
}
void cal() {
slove();
while(q--) {
int aa,bb,cc,dd;
cin>>aa>>bb>>cc>>dd;
cout<<dp[aa][bb][cc][dd]<<endl;
}
}
void output() {
}
int main() {
while(true) {
init();
if(input())return 0;
cal();
output();
}
return 0;
}