METEORAK

分析

设 \(dp[l][r]\) 表示第 \(l\) 到 \(r\) 行的答案，可以发现它由 \(f[l][r],dp[l][r+1],dp[l+1][r]\) 转移而来。

关键就是求出 \(f[l][r]\)，考虑枚举 \(r\)，那么实际上组成了一些柱状图，用单调栈维护最大的矩形宽度然后更新一下即可

代码

#include 
#include 
using namespace std;
const int N=1511; bool ban[N][N];
int dp[N][N],n,m,k,h[N],w[N],st[N],Top;
int iut(){
	int ans=0; char c=getchar();
	while (!isdigit(c)) c=getchar();
	while (isdigit(c)) ans=ans*10+c-48,c=getchar();
	return ans;
}
void print(int ans){
	if (ans>9) print(ans/10);
	putchar(ans%10+48);
}
void Max(int &x,int y){x=x>y?x:y;}
int main(){
	n=iut(),m=iut(),k=iut();
	for (int i=1;i<=k;++i){
		int x=iut(),y=iut();
		ban[x][y]=1;
	}
	for (int i=1;i<=n;++i){
		for (int j=1;j<=m;++j)
		if (ban[i][j]) h[j]=0;
		    else ++h[j];
		Top=0;
		for (int j=1;j<=m+1;++j){
			int width=0;
			while (Top&&h[st[Top]]>=h[j]){
				width+=w[Top];
				Max(dp[i-h[st[Top]]+1][i],width);
				--Top;
			}
			st[++Top]=j,w[Top]=width+1;
		}
		for (int j=1;j