這是針對倉鼠窩的題解

另外兩題是要稍微改一下的雙倍經驗

題意

屠龍寶刀點擊就送

01矩陣，求全1的子矩陣數目

解析

#include<cstdio>
#define int long long
int n,m,area[3005][3005];
int low[3005];//low[j]表示第j列最高的破壞點（0）
int f[3005];//f[i]表示當前計算的這一行，第i列的答案 
int s[3005],top;//手寫棧 
int ans;
signed main(){
	scanf("%lld%lld",&n,&m);
	for(int i=1;i<=n;i++)
		for(int j=1;j<=m;j++)
			scanf("%lld",&area[i][j]);
	for(int i=1;i<=n;i++)
		for(int j=1;j<=m;j++){
			if(!area[i][j])low[j]=i;//在這個時候更新最高破壞點 
			while(top&&low[s[top]]<low[j])top--;
			//如果一個選手比你小，還比你強，那我們讓他退役...... qvq  
            //注意是i小的強（維護單增殼）......
			ans+=(f[j]=f[s[top]]+(i-low[j])*(j-s[top])); 
			//使用手寫棧，棧空時棧頂元素值為0，而非RE 
			//其實這一行好多題解都有點難懂，我寫的不太一樣
            //我寫的是由s[top]轉移而來，而不是從j-1
			//可以對著洛谷題解的圖理解，但是那張圖的矩形顏色跟我想的不一樣啊（藍色區域為什么啊qvq） 
            //我這里加的是粉色矩形，挺好理解的吧qvq
			s[++top]=j; 
			//我習慣這個時候再入棧，多舒服 
		}
		top=0;//每一行新開一個棧 
	printf("%lld
",ans);
}

附圖

洛谷題解那張圖（侵刪

P.S.

其實我自己寫的時候不喜歡這樣的碼風，放出來的時候覺得這樣的碼風才好看wqvq

總結

以上是生活随笔為你收集整理的单调栈 洛谷 P3400仓鼠窝 P1191 矩形 P1950 长方形的全部內容，希望文章能夠幫你解決所遇到的問題。

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