273 条题解
-
15
PowderHan LV 10 @ 2017-05-07 22:22:54
/* 一个很经典类型的dp~ 如果用悬线法或者单调栈因为数据不大所以特判一下也是可以AC的 但是有更简单的dp做法 我们f[i,j]表示点(i,j)为正方形右下角的点时的最小边长 那么一个以(i,j)为右下角的正方形能否接上别的更大的正方形 必然是和(i-1,j-1) (i-1,j) (i,j-1)有关 这样的话我们就可以尝试f[i][j]的转移 根据短板原理咯~f[i][j]到底能扩展到多大必然是三个中的最小值 这样就会有f[i][j]=min(f[i-1][j-1],f[i-1][j],f[i][j-1])+1 前提是(i,j)是完整的 这样我们很容易看到其实如果我们按照1...n 1...m输入的顺序 其实对于每个f[i][j] 它需要的三个状态已经推了出来 这样的话其实根本没有必要储存这个图 而是可以直接一个一个读入(i,j)的情况 如果(i,j)不是完好的话那么必然f[i][j]就是0 不需要任何操作 如果是完好的那么就可以尝试转移了~ 这样复杂度就是O(nm)的 完全可以直接秒杀 */ #include <iostream> #include <cstdio> #include <algorithm> #include <cstring> using namespace std; const int MAXN=1005; int f[MAXN][MAXN]; int n,m; int ans; void init() { scanf("%d%d",&n,&m); } void DP() { int tmp; for(int i=1;i<=n;i++) for(int j=1;j<=m;j++) { scanf("%d",&tmp); if(tmp) f[i][j]=min(f[i-1][j-1],min(f[i-1][j],f[i][j-1]))+1; ans=max(ans,f[i][j]); } printf("%d\n",ans); } int main() { init(); DP(); } -
1
//百题AC纪念 #include<iostream> #include<cstring> using namespace std; int map[1010][1010],pan[1010][1010]; int Min(int a,int b,int c) { int d; d=min(a,b); d=min(d,c); return d; } int main() { int n,i,m,k,maxn=0; cin>>n>>m; for(i=1;i<=n;i++) for(k=1;k<=m;k++) cin>>map[i][k]; for(i=1;i<=n;i++) { for(k=1;k<=m;k++) { if(map[i][k]) { pan[i][k]=Min(pan[i-1][k-1],pan[i-1][k],pan[i][k-1])+1; maxn=max(pan[i][k],maxn); } else pan[i][k]=0; } } cout<<maxn; return 0; } -
0
#include <iostream> //盖房子 #include <algorithm> using namespace std; const int MaxN = 1010; int n, m; int w[MaxN][MaxN]; int dp[MaxN][MaxN]; //dp[i][j]: 以(i, j)为右下角顶点的最大正方形的边长 int Maxa = 0; void DP() { for (int i = 1; i <= n; i++) for (int j = 1; j <= m; j++) { if(w[i][j]) dp[i][j] = min({ dp[i - 1][j - 1], dp[i][j - 1], dp[i - 1][j] }) + w[i][j]; Maxa = max(Maxa, dp[i][j]); } cout << Maxa << endl; } int main() { cin >> n >> m; for (int i = 1; i <= n; i++) for (int j = 1; j <= m; j++) cin >> w[i][j]; DP(); system("pause"); return 0; } -
0
/* dp */ #include<cstdio> #include<cstring> #include<algorithm> using namespace std; int m,n,ans; int f[1100][1100],map[1100][1100]; int main() { scanf("%d%d",&n,&m); for(int i=1;i<=n;i++) for(int j=1;j<=m;j++) scanf("%d",&f[i][j]); for(int i=1;i<=n;i++) map[i][1]=f[i][1]; for(int i=1;i<=m;i++) map[1][i]=f[1][i]; for(int i=2;i<=n;i++) for(int j=2;j<=m;j++) { map[i][j]=min(map[i-1][j],map[i-1][j-1]); map[i][j]=min(map[i][j],map[i][j-1])+1; if(f[i][j]==0) map[i][j]=0; } for(int i=1;i<=n;i++) for(int j=1;j<=m;j++) if(map[i][j]>ans) ans=map[i][j]; printf("%d",ans); return 0; } -
0
//看了大神的题解之后写的 #include<cstdio> int min(int a,int b,int c){ if(a<b)return a<c?a:(b<c?b:c); else return b<c?b:(a<c?a:c); } int main(){ int n,m,max=0; scanf("%d%d",&n,&m); int *dt[n]; for(int i=0;i<n;i++){ dt[i]=new int[m]; for(int j=0;j<m;j++){ scanf("%d",&dt[i][j]); if(dt[i][j]&&i&&j)dt[i][j]+=min(dt[i-1][j],dt[i][j-1],dt[i-1][j-1]); if(dt[i][j]>max)max=dt[i][j]; } } printf("%d",max); return 0; } -
0
#include <iomanip> #include <iostream> #include <queue> #include <vector> #include <algorithm> #include <string> #include <cstring> #include <cstdlib> #include <cmath> #include <cstdio> using namespace std; int a[1010][1010],f[1010][1010]; int main() { ios :: sync_with_stdio(false); int n,m,k,b=-999; cin>>n>>m; for(int i=1;i<=n;i++) for(int j=1;j<=m;j++) cin>>a[i][j]; for(int i=1;i<=n;i++) for(int j=1;j<=m;j++) if(a[i][j]==1) f[i][j]=min(a[i][j-1],min(a[i-1][j],a[i-1][j-1]))+1; for(int i=1;i<=n;i++) for(int j=1;j<=m;j++)//最后再暴搜一遍 b=max(f[i][j],b); cout<<b<<endl; return 0; } -
0
fhqfjevfhp LV 5 @ 2018-01-18 11:59:36
-
0
westfallon LV 8 @ 2017-10-18 12:29:35
不怎么纯粹的dp 轻喷
#include<iostream> #include<cstring> #include<cstdio> #include<cstdlib> #include<cmath> #include<algorithm> using namespace std; int n,m,maxn=1; bool a[1010][1010],dp[1010][1010][1010]; bool judge(int x1,int y1,int x2,int y2) { for(int i=x1;i<=x2;i++) if(!a[i][y2]) return 0; for(int i=y1;i<=y2;i++) if(!a[x2][i]) return 0; return 1; } void ddpp(int i,int j) { for(int k=2;k<=min(n-i,m-j);k++) { if(!dp[i][j][k-1]) { dp[i][j][k]=0; return; } else if(judge(i,j,i+k-1,j+k-1)) { dp[i][j][k]=1; maxn=max(maxn,k); } else { dp[i][j][k]=0; return ; } } } int main() { cin>>n>>m; for(int i=1;i<=n;i++) { for(int j=1;j<=m;j++) { cin>>a[i][j]; if(a[i][j]) dp[i][j][1]=1; else dp[i][j][1]=0; } } for(int i=1;i<=n;i++) { for(int j=1;j<=m;j++) { ddpp(i,j); } } cout<<maxn<<endl; return 0; } -
0
真的非常的容易~~~
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
int n,m,x,ans;
int f[1001][1001];
int main()
{
cin>>n>>m;
for(int i=1;i<=n;i++)
{
for(int j=1;j<=m;j++)
{
cin>>x;
if(x==1) f[i][j]=min(f[i-1][j],min(f[i][j-1],f[i-1][j-1]))+1;
else f[i][j]=0;
ans=max(ans,f[i][j]);
}
}
cout<<ans;
} -
0
1156400231 LV 7 @ 2017-09-03 17:25:10
var
i,j,k,n,m,x,s,t:longint;
a,f:array [0..1000,0..1000] of longint;
function max(x,y:longint):longint;
begin
if x>y then max:=x
else max:=y;
end;
begin
read(n,m);
for i:=1 to n do
for j:=1 to m do
begin
read(a[i,j]);
if a[i,j]=1 then f[i,j]:=1;
end;
for i:=1 to n do
begin
for j:=1 to m do
if (a[i-1,j-1]=1) and (a[i,j]=1) then
begin
t:=0;
for k:=j-f[i-1,j-1] to j-1 do
if a[i,k]=0 then t:=1;
for k:=i-f[i-1,j-1] to i-1 do
if a[k,j]=0 then t:=1;
if t=0 then f[i,j]:=max(f[i,j],f[i-1,j-1]+1);
end;
end;
s:=0;
for i:=1 to n do
for j:=1 to m do
if f[i,j]>s then s:=f[i,j];
write(s);
end. -
0
然而并不需要dp，前缀和即可~
#include<stdio.h> int n,m,s[1010][1010],a=1; int g(int dx,int dy,int x,int y){ return s[x][y]-s[dx][y]-s[x][dy]+s[dx][dy]; } int main(){ scanf("%d%d",&n,&m); for(int i=1;i<=n;++i) for(int j=1;j<=m;++j){ scanf("%d",s[i]+j); s[i][j]^=1; s[i][j]+=s[i-1][j]+s[i][j-1]-s[i-1][j-1]; } for(int i=1;i<=n;++i) for(int j=1;j<=m;++j) while(i+a<=n&&j+a<=m&&g(i-1,j-1,i+a,j+a)==0) a++; printf("%d\n",a); } -
0
Sky1231 (sky1231) LV 10 @ 2017-03-12 14:02:28
#include <cstdio> #include <cstring> #include <algorithm> #define r 1000 using namespace std; int n,m,ans=0,f[r+1][r+1]; int main() { scanf("%d%d",&n,&m); memset(f,0,sizeof(f)); for (int i=1;i<=n;i++) for (int j=1;j<=m;j++) scanf("%d",&f[i][j]); for (int i=1;i<=n;i++) for (int j=1;j<=m;j++) if (f[i][j]!=0) { f[i][j]+=min(f[i-1][j-1],min(f[i-1][j],f[i][j-1])); ans=max(ans,f[i][j]); } printf("%d\n",ans); } -
0
3037989264 LV 8 @ 2017-02-08 09:18:14
用了快半小时才想通
c++
#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cmath>
#include<cstring>
#include<algorithm>
using namespace std;
int n,m,ans;
int f[1001][1001];
int main()
{
scanf("%d%d",&n,&m);
for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++)
{
scanf("%d",&f[i][j]);
if(f[i][j])f[i][j]+=min(f[i-1][j],min(f[i-1][j-1],f[i][j-1]));
ans=max(ans,f[i][j]);
}
printf("%d",ans);
return 0;
}
-
0
冻龟
以每个可施工点为工地右下角，该点值即为工地大小
比较每个点左，上，左上三个点的值，取最小值+1即为该点值
注意边界处理#include<cstdio> #include<cmath> int n,m,i,j,t,max; int map[1001][1001],a[1001][1001]; int main() { scanf("%d%d",&n,&m); for (i=1;i<=n;i++) for (j=1;j<=m;j++) scanf("%d",&map[i][j]); for (i=1;i<=n;i++) for (j=1;j<=m;j++) if (map[i][j]==1) { a[i][j]=a[i-1][j-1]; if (a[i-1][j]<a[i][j]) a[i][j]=a[i-1][j]; if (a[i][j-1]<a[i][j]) a[i][j]=a[i][j-1]; a[i][j]++; if (a[i][j]>t) t=a[i][j]; } printf("%d",t); return 0; } -
0
说好的需要10分钟呢？五分钟搞定
uses math;
var
--a,f:array[0..2000,0..2000] of longint;
--i,j,k,n,m:longint;
begin
--readln(n,m);
--for i:=1 to n do
----for j:=1 to m do
------read(a[i,j]);
--k:=0;
--for i:=1 to n do
----for j:=1 to m do
------if a[i,j]=1 then
--------begin
----------f[i,j]:=min(min(f[i,j-1],f[i-1,j]),f[i-1,j-1])+1;
----------k:=max(k,f[i,j]);
--------end;
--write(k);
end. -
0
#include<iostream>
#include<cstring>
using namespace std;
int Map[1010][1010]={0},f[1010][1010]={0};
int main()
{
int n,m,ans=0; cin>>n>>m;
for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++)
cin>>Map[i][j];for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++)
{
if(Map[i][j]==1) f[i][j]++;
if(Map[i][j]!=0&&Map[i-1][j]!=0&&Map[i][j-1]!=0&&Map[i-1][j-1]!=0)
f[i][j]=min(f[i-1][j],max(f[i][j-1],f[i-1][j-1]))+1;
ans=max(ans,f[i][j]);
}
cout<<ans;return 0;
}f[i][j]=min(f[i-1][j],max(f[i][j-1],f[i-1][j-1]))+1;取了最大值结果40分 数据这么水
-
0
feng_lingsong LV 9 @ 2016-08-30 10:46:21
简单dp
#include <cstdio>
#include <cstdlib>
#include <algorithm>
#define rep(i, x, y) for (int i = x; i <= y; ++i)using namespace std;
int left[1005][1005], up[1005][1005], map[1005][1005], f[1005][1005];
int n, m;int main(int argc, const char *argv[]) {
scanf("%d%d", &n, &m);
rep(i, 1, n) {
rep(j, 1, m) {
scanf("%d", &map[i][j]);
}
}
rep(i, 1, n) {
int cnt = 0;
rep(j, 1, m) {
if (map[i][j] == 0) {cnt = 0; continue;}
left[i][j] = ++cnt;
}
}
rep(j, 1, m) {
int cnt = 0;
rep(i, 1, n) {
if (map[i][j] == 0) {cnt = 0; continue;}
up[i][j] = ++cnt;
}
}
int ans = 0;
rep(i, 1, n) rep(j, 1, m) {
if (!map[i][j]) continue;
f[i][j] = min(f[i - 1][j - 1], min(left[i][j - 1], up[i - 1][j])) + 1;
ans = max(ans, f[i][j]);
}
printf("%d\n", ans);
return 0;
} -
0
/*
f[i,j]表示点（i，j）为正方形右下角的点时的最小边长，
因为知道正方形的话，这一点的状态只由点（i-1，j-1）（i-1，j）（i，j-1）决定
可优化处理，每个点的状态单独读入处理
*/
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
using namespace std;bool x;
int n,m;
int f[1002][1002];
int ans=-1;int main()
{
cin>>n>>m;
for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++)
{
cin>>x;
if(x)
f[i][j]=min(f[i-1][j-1],min(f[i-1][j],f[i][j-1]))+1;
ans=max(ans,f[i][j]);
}
cout<<ans<<endl;
return 0;
} -
0
1749046292 LV 8 @ 2016-07-25 21:09:12
#include<iostream> using namespace std; int f[1005][1005],m,n,ans=0; int main() { cin>>n>>m; for(int i=1;i<=n;i++) for(int j=1;j<=m;j++) cin>>f[i][j]; for(int i=2;i<=n;i++) for(int j=2;j<=m;j++) if(f[i][j]==1) f[i][j]+=min(f[i-1][j],min(f[i][j-1],f[i-1][j-1])); for(int i=1;i<=n;i++) for(int j=1;j<=m;j++) ans=max(ans,f[i][j]); cout<<ans; return 0; }
PowderHan
LV 10
@ 2017-05-07 22:22:54
