网站开发 技术指标,官网mini1cn下载迷你世界登录,asp.net 网站图标,建设网站是什么关系正题 题目大意
一个n∗nn*nn∗n的矩阵#xff0c;然后有些位置破损。求可以剪出多少个不破损的矩形。 解题思路
预处理upi,jup_{i,j}upi,j表示从(i,j)(i,j)(i,j)向上多少格子都是非破损格子。
然后我们枚举下界LowLowLow#xff0c;将图像变成一个下部平整的条形图…正题 题目大意
一个n∗nn*nn∗n的矩阵然后有些位置破损。求可以剪出多少个不破损的矩形。 解题思路
预处理upi,jup_{i,j}upi,j表示从(i,j)(i,j)(i,j)向上多少格子都是非破损格子。
然后我们枚举下界LowLowLow将图像变成一个下部平整的条形图第iii个位置高度为uplow,iup_{low,i}uplow,i。为了方便阐述我们统一用hih_ihi代表upLow,iup_{Low,i}upLow,i。
然后我们获得一个条形图后我们要求有多少个矩形经过底部。考虑像Largest Rectangle in a Histogram这一题一样进行计算。
现在栈中维护若干个单调递增的条形 每个条形有不同的宽度 如(现在的宽度暂时都为1) 现在若加入一条高度为666的条形则直接加入。
但若加入一条高度为444的块我们需要弹出末尾的块并统计答案。 我们用WideWideWide表示目前弹出的块的宽度和(要包括现在弹出的那条)。然后我们发现在这个块的右边(已经弹出的部分)都比它要高也就是在1∼hnow1\sim h_{now}1∼hnow中任意取一个高度都可以也就是Wide∗hnowWide*h_{now}Wide∗hnow种取法。
但是如果现在弹出的块宽度不为111呢? 我们会发现只需要经过蓝色的点的矩形都可以被统计到右边这一块弹出时的答案
那这种有多少个呢 首先是穿过这个点的也就是左边的个数乘上右边的格子数。 而从这个点出发的就是左边的格子数加上右边的格子数。 然后单独这个点就是111。
我们从新定义WideWideWide不计算上现在弹出的块的宽度那每次累计的答案数为 (widenow∗Widewidenode)∗hnow(wide_{now}*Widewide_{node})*h_{now}(widenow∗Widewidenode)∗hnow codecodecode
#includecstdio
#includecstring
#includealgorithm
#includestack
#define ll long long
using namespace std;
const ll N1100;
ll n,f[N][N],ans,up[N][N],weigh,wigh[N];
stackint s;
char v[N][N];
int main()
{scanf(%lld,n);for(ll i1;in;i)scanf(%s,v[i]1);for(ll i1;in;i){for(ll j1;jn;j){if(v[i][j]0) up[i][j]up[i-1][j]1;else up[i][j]0;}}for(ll i1;in;i){for(ll j1;jn;j){weigh0;while(!s.empty()up[i][j]up[i][s.top()]){ans(weigh*wigh[s.top()]wigh[s.top()])*up[i][s.top()];weighwigh[s.top()];s.pop();}s.push(j);wigh[j]weigh1;}weigh0;while(!s.empty()){ans(weigh*wigh[s.top()]wigh[s.top()])*up[i][s.top()];weighwigh[s.top()];s.pop();}}printf(%lld,ans);
}
