https://ac.nowcoder.com/acm/contest/882/H
正确的办法：dp1[i][j]表示以i,j为底的矩形的高。得到dp1之后，dp2[i][j]表示以dp1[i][j]悬线向左能移动的极限（用单调栈）。
维护最后答案的时候单调栈是>=的，这样同高的就不会重复计算。
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define ERR(args...) { string _s = #args; replace(_s.begin(), _s.end(), ',', ' '); stringstream _ss(_s); istream_iterator<string> _it(_ss); err(_it, args); }
void err(istream_iterator<string> it) {cerr << "\n";}
template<typename T, typename... Args>
void err(istream_iterator<string> it, T a, Args... args) {
cerr << *it << "=" << a << ", ";
err(++it, args...);
}
#define ERR1(arg,n) { cerr<<""<<#arg<<"=\n "; for(int i=1;i<=n;i++) cerr<<arg[i]<<" "; cerr<<"\n"; }
#define ERR2(arg,n,m) { cerr<<""<<#arg<<"=\n"; for(int i=1;i<=n;i++) { cerr<<" "; for(int j=1;j<=m;j++)cerr<<arg[i][j]<<" "; cerr<<"\n"; } }
#define REP(i, a, b) for(int i = a; i <= b; ++i)
int n, m;
char g[1005][1005];
int dp1[1005][1005], dp2[1005][1005];
int stk1[1005], top;
int max1, max2;
void update(int val) {
if(val > max2)
max2 = val;
if(max2 > max1) {
int t = max2;
max2 = max1;
max1 = t;
}
}
int main() {
#ifdef Yinku
freopen("Yinku.in", "r", stdin);
//freopen("Yinku.out", "w", stdout);
//freopen("Yinku.err", "w", stderr);
#endif // Yinku
scanf("%d%d", &n, &m);
REP(i, 1, n) scanf("%s", g[i] + 1);
REP(j, 1, m) dp1[1][j] = (g[1][j] - '0');
REP(i, 2, n) REP(j, 1, m) dp1[i][j] = (g[i][j] - '0') ? (dp1[i - 1][j] + 1) : 0;
REP(i, 1, n) {
dp2[i][1] = 1;
top=0;
stk1[++top]=1;
REP(j, 2, m) {
int tmp=j;
while(top&&dp1[i][stk1[top]]>=dp1[i][j]){
tmp=stk1[top];
--top;
}
dp2[i][j]=tmp<j?dp2[i][tmp]:j;
stk1[++top]=j;
}
}
//ERR2(dp1, n, m);
//ERR2(dp2, n, m);
max1 = 0, max2 = 0;
REP(i, 1, n) {
top = 0;
REP(j, 1, m) {
while(top && dp1[i][stk1[top]] >= dp1[i][j]) {
int h = dp1[i][stk1[top]];
int w = j-1-dp2[i][stk1[top]]+1;
//ERR(stk1[top],w*h);
if(w && h) {
update(w * h);
update((w - 1) *h);
update(w * (h - 1));
}
--top;
}
stk1[++top] = j;
}
while(top) {
int h = dp1[i][stk1[top]];
int w = m-dp2[i][stk1[top]]+1;
//ERR(stk1[top],w*h);
if(w && h) {
update(w * h);
update((w - 1) *h);
update(w * (h - 1));
}
--top;
}
//cerr<<endl;
}
printf("%d\n", max2);
}
小心这个样例
5 6
110000
011000
101100
110100
111010
5 6
110010
011111
101110
110111
111010
错误代码：
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define ERR(args...) { string _s = #args; replace(_s.begin(), _s.end(), ',', ' '); stringstream _ss(_s); istream_iterator<string> _it(_ss); err(_it, args); }
void err(istream_iterator<string> it) {cerr << "\n";}
template<typename T, typename... Args>
void err(istream_iterator<string> it, T a, Args... args) {
cerr << *it << "=" << a << ", ";
err(++it, args...);
}
#define ERR1(arg,n) { cerr<<""<<#arg<<"=\n "; for(int i=1;i<=n;i++) cerr<<arg[i]<<" "; cerr<<"\n"; }
#define ERR2(arg,n,m) { cerr<<""<<#arg<<"=\n"; for(int i=1;i<=n;i++) { cerr<<" "; for(int j=1;j<=m;j++)cerr<<arg[i][j]<<" "; cerr<<"\n"; } }
#define REP(i, a, b) for(int i = a; i <= b; ++i)
int n, m;
char g[1005][1005];
int dp[1005][1005];
int stk[1005], top;
int max1, max2;
void update(int val) {
if(val > max2)
max2 = val;
if(max2 > max1) {
int t = max2;
max2 = max1;
max1 = t;
}
}
int main() {
#ifdef Yinku
freopen("Yinku.in", "r", stdin);
#endif // Yinku
scanf("%d%d",&n,&m);
REP(i, 1, n) scanf("%s", g[i] + 1);
REP(j, 1, m) dp[1][j] = (g[1][j] - '0');
REP(i, 2, n) REP(j, 1, m) dp[i][j] = (g[i][j] - '0') ? (dp[i - 1][j] + 1) : 0;
ERR2(dp, n, m);
max1 = 0, max2 = 0;
REP(i, 1, n) {
top = 0;
REP(j, 1, m) {
while(top && dp[i][stk[top]] > dp[i][j]) {
int h = dp[i][stk[top]];
int w = (j - 1) - stk[top]+1;
if(w && h) {
update(w * h);
update((w - 1) *h);
update(w * (h - 1));
}
--top;
}
stk[++top] = j;
}
while(top) {
int h = dp[i][stk[top]];
int w = m - stk[top];
if(w && h) {
update(w * h);
update((w - 1) *h);
update(w * (h - 1));
}
--top;
}
}
printf("%d\n", max2);
}
错误在于虽然把3弹出来了但其实2是可以延伸过去的。也就是单调栈一直弹出东西的时候都是可以延伸过去的，那干脆演一波算了。
虽然通过了错误代码1，但是没有计算悬线向左最远距离的方法是错的。
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define ERR(args...) { string _s = #args; replace(_s.begin(), _s.end(), ',', ' '); stringstream _ss(_s); istream_iterator<string> _it(_ss); err(_it, args); }
void err(istream_iterator<string> it) {cerr << "\n";}
template<typename T, typename... Args>
void err(istream_iterator<string> it, T a, Args... args) {
cerr << *it << "=" << a << ", ";
err(++it, args...);
}
#define ERR1(arg,n) { cerr<<""<<#arg<<"=\n "; for(int i=1;i<=n;i++) cerr<<arg[i]<<" "; cerr<<"\n"; }
#define ERR2(arg,n,m) { cerr<<""<<#arg<<"=\n"; for(int i=1;i<=n;i++) { cerr<<" "; for(int j=1;j<=m;j++)cerr<<arg[i][j]<<" "; cerr<<"\n"; } }
#define REP(i, a, b) for(int i = a; i <= b; ++i)
int n, m;
char g[1005][1005];
int dp1[1005][1005], dp2[1005][1005];
int stk1[1005], top;
int max1, max2;
void update(int val) {
if(val > max2)
max2 = val;
if(max2 > max1) {
int t = max2;
max2 = max1;
max1 = t;
}
}
int main() {
#ifdef Yinku
freopen("Yinku.in", "r", stdin);
#endif // Yinku
scanf("%d%d", &n, &m);
REP(i, 1, n) scanf("%s", g[i] + 1);
REP(j, 1, m) dp1[1][j] = (g[1][j] - '0');
REP(i, 2, n) REP(j, 1, m) dp1[i][j] = (g[i][j] - '0') ? (dp1[i - 1][j] + 1) : 0;
REP(i, 1, n) dp2[i][1] = 1;
REP(i, 1, n) REP(j, 2, m) dp2[i][j] = (dp1[i][j] <= dp1[i][j - 1]) ? (dp2[i][j - 1] + 1) : 1;
ERR2(dp1, n, m);
ERR2(dp2, n, m);
max1 = 0, max2 = 0;
REP(i, 1, n) {
top = 0;
REP(j, 1, m) {
while(top && dp1[i][stk1[top]] > dp1[i][j]) {
int h = dp1[i][stk1[top]];
int w = dp2[i][stk1[top]];
if(w && h) {
update(w * h);
update((w - 1) *h);
update(w * (h - 1));
}
--top;
}
stk1[++top] = j;
}
while(top) {
int h = dp1[i][stk1[top]];
int w = dp2[i][stk1[top]];
if(w && h) {
update(w * h);
update((w - 1) *h);
update(w * (h - 1));
}
--top;
}
}
printf("%d\n", max2);
}