脚本宝典收集整理的这篇文章主要介绍了P3400【仓鼠窝 】,脚本宝典觉得挺不错的,现在分享给大家,也给大家做个参考。
思路清奇,代码简洁的好题
问题大体分两部:
考虑从右下角开始,如果有0已经挡住了矩阵,那么更靠左、上的0都卵用没有->单调栈
#include<bits/stdc++.h>
using namespace std;
int n,m,a[3005][3005];
int up[3005],s[3005],top;
long long sum[3005],ans=0;
int main()
{
scanf("%d%d",&n,&m);
for(int i=1;i<=n;i++)
{
for(int j=1;j<=m;j++)
{
scanf("%d",&a[i][j]);
}
}
for(int i=1;i<=n;i++)
{
top=0;//维护最近的0
for(int j=1;j<=m;j++)
{
if(!a[i][j]) up[j]=i;//墙
while(top&&up[s[top]]<up[j]) top--; //远的0不要
s[++top]=j;//高度
sum[top]=sum[top-1]+(i-up[s[top]])*(s[top]-s[top-1]);//左边的答案继承+新形成的矩形方案(新的最大矩形长 ×宽)
ans+=sum[top];
}
}
printf("%lld",ans);
return 0;
}
以上是脚本宝典为你收集整理的P3400【仓鼠窝 】全部内容,希望文章能够帮你解决P3400【仓鼠窝 】所遇到的问题。
本图文内容来源于网友网络收集整理提供,作为学习参考使用,版权属于原作者。
如您有任何意见或建议可联系处理。小编QQ:384754419,请注明来意。