题解

273 条题解

  • 15
    @ 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
    @ 2017-10-02 16:10:09
    //百题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
    @ 2020-03-03 17:17:35
    #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
    @ 2018-08-08 11:46:51
    /*
    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
    @ 2018-03-19 21:33:47
    //看了大神的题解之后写的
    #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
    @ 2018-02-05 13:20:43
    #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
    @ 2018-01-18 11:59:36
  • 0
    @ 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
    @ 2017-09-07 19:51:41

    真的非常的容易~~~

    #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
    @ 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
    @ 2017-05-26 20:17:27

    然而并不需要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
    @ 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
    @ 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
    @ 2016-11-06 13:38:30

    冻龟
    以每个可施工点为工地右下角,该点值即为工地大小
    比较每个点左,上,左上三个点的值,取最小值+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
    @ 2016-10-22 13:11:29

    说好的需要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
    @ 2016-10-06 15:21:15

    side[i][j]=min(side[i-1][j], side[i][j-1], side[i-1][j-1]);
    side[1][j]=a[1][j];
    side[i][1]=a[i][1];
    ans=max(side[i][j]);

  • 0
    @ 2016-09-16 15:16:35

    #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
    @ 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
    @ 2016-08-13 14:02:09

    /*
    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
    @ 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;
    }
    

信息

ID
1057
难度
4
分类
动态规划 点击显示
标签
(无)
递交数
6649
已通过
3066
通过率
46%
被复制
8
上传者