大佬帮忙看下有几个点会错

#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#include <cmath>
using namespace std;
const int maxn=2005;
int n,m,sum[maxn][maxn],s[maxn],l[maxn],a[maxn][maxn],dp[maxn][maxn],ans,ans1;
void make_it(int h[]){
int top=0,len=0;
s[top]=0,l[top]=0;
for(int i=1;i<=m;i++){
if(h[i]>=s[top]&&h[i]!=h[i-1]){
s[++top]=h[i];
l[top]=1;
}
else{
len=0;
while(top&&s[top]>h[i]){
len+=l[top];
ans=max(ans,len*s[top]);
top--;
}
s[++top]=h[i];
l[top]=len+1;
}
}
len=0;
while(top){
len+=l[top];
ans=max(ans,len*s[top]);
top--;
}
}
int main(){
scanf("%d%d",&n,&m);
for(int i=1;i<=m;i++)sum[1][i]=1;
for(int i=1;i<=n;i++){
for(int j=1;j<=m;j++){
scanf("%d",&a[i][j]);
dp[i][j]=1;
if(a[i][j]!=a[i-1][j])
sum[i][j]=sum[i-1][j]+1;
else sum[i][j]=1;
}
}
for(int i=1;i<=n;i++){
for(int j=1;j<=m;j++){
if(a[i][j]+a[i-1][j]+a[i-1][j-1]+a[i][j-1]!=2||a[i][j]==a[i][j-1]||a[i][j]==a[i-1][j])continue;
dp[i][j]+=min(dp[i-1][j],min(dp[i-1][j-1],dp[i][j-1]));
if(dp[i][j]>ans)ans=dp[i][j];
}
}
// puts("");
// for(int i=1;i<=n;i++){
// for(int j=1;j<=m;j++){
// printf("%d ",sum[i][j]);
// }
// puts("");
// }
if(ans!=0)printf("%d\n",ans*ans);
else printf("%d\n",1);
ans=1;
for(int i=1;i<=n;i++)make_it(sum[i]);
printf("%d",ans);

return 0;
}

1 条评论

  • 1

信息

ID
1351
难度
7
分类
动态规划 | 单调性DP数据结构 | 点击显示
标签
(无)
递交数
1038
已通过
234
通过率
23%
被复制
6
上传者