140 条题解

  • 5
    @ 2018-09-06 15:46:17
    //看到楼上的大佬是n平方的做法,但由于这道题很水,n的三次方也可以过
    //处理出每个点向右可以延伸多远,之后每一个点暴力寻找
    //数组要开大一点
    #include<iostream>
    using namespace std;
    char map[220][220];
    int dp[220][220],maxn[220][220];
    int main()
    {
        int n,i,j,k,now,nx,ans=0;
        cin>>n;
        for(i=1;i<=n;i++)
         for(j=1;j<=2*n-2*i+1;j++)
          cin>>map[i][j];
        for(i=1;i<=n;i++)
         for(j=2*n-2*i+1;j>0;j--)
          if(map[i][j]=='-')
           maxn[i][j]=maxn[i][j+1]+1;
        for(i=n;i>0;i--)
         for(j=1;j<=2*n-2*i+1;j++)
           if(map[i][j]=='-'&&j%2==1)
            {
                 for(k=i;k>0;k--)
                  if(maxn[k][j]<2*(i-k)+1)
                   break;
                 ans=max(ans,(i-k)*(i-k));
            }
        cout<<ans;
        return 0;
    }
    
  • 3
    @ 2017-05-07 22:25:47
    /*
    一道找一个正三角形中包含的最大正三角形
    {输入文件中出现空格,且空格只是为了保持整个三角形的形状。}
    也是蛮烦人的这个东西,就只能老老实实用scanf输入吧
    动态规划,表示没看懂题目
    以为是要求向上和向下之和?
    但好像答案是向下的?或者是数据太弱?
    注意要判断ODD(奇偶性)
    (1,2)(1,3)(1,4)
             (2,3)
    显然不能形成一个三角形
    所以我们对于能构成个向下的更大的三角形的顶点坐标一定有
    x,y同奇偶,也只有满足这个条件才能继续递推
    设f[i][j]表示以(i,j)为顶点的最大的正三角形规模
    (规模1有1个,规模2有四个,规模3有九个QWQ)
    则有
    如果i,j同奇偶
    并且满足a[i-1][j]=='-'&&a[i-1][j-1]=='-'&&a[i-1][j+1]=='-'
    即这个顶点的上面一行的三个扩展点都要是可行点(就是穿了夏季校服的)
    如果满足这两个条件,就说明这个点是可以尝试更新更优解的
    f[i][j]=min(min(f[i-1][j-1]+1,f[i-1][j+1]+1),f[i-2][j]+2);
    前两个就是上面的两个角顶点所能扩展的值+自身这一层的一个规模
    而第三个就是要正对上面两行的那个点能扩展的最大值了
    嗯因为如果要扩展到下面行(和下下面行),那么肯定是要取最小值了
    (自己好好体会~很难说明白)
    Orz经典题目了 也蛮好的
    */
    #include <iostream>
    #include <cstdio>
    #include <algorithm>
    #include <cstring>
    using namespace std;
    
    const int MAXN=125;//开105最后一个点会爆啊Orz
    char a[MAXN][MAXN];
    int f[MAXN][MAXN];
    int n;
    int ans;
    
    void init()
    {
        scanf("%d",&n);
        for(int i=1;i<=n;i++)
            for(int j=i;j<i+2*n+1-2*i;j++)
                scanf(" %c",&a[i][j]);
        for(int i=1;i<=2*n-1;i++)
            if(a[1][i]=='-')
                f[1][i]=1,ans=1;
    }
    
    int main()
    {
        init();
        for(int i=2;i<=n;i++)
            for(int j=i;j<=2*n-i;j++)
                if(a[i][j]=='-'&&((i+j)&1)==0)
                {
                    f[i][j]=1;
                    if(a[i-1][j]=='-'&&a[i-1][j-1]=='-'&&a[i-1][j+1]=='-')
                        f[i][j]=min(min(f[i-1][j-1]+1,f[i-1][j+1]+1),f[i-2][j]+2);
                    ans=max(ans,f[i][j]);
                }
        cout<<ans*ans<<endl;
        return 0;
    }
         
    
  • 1
    @ 2020-03-05 17:31:01
    //分两步遍历:
    //1. 从上往下遍历单号
    //2. 从下往上遍历双号
    //注意dp数组最大值要是n的两倍, 一开始被坑了...
    //dp表示的是三角形的边, 要转换为小三角形个数
    #include <iostream>         //迎春舞会之集体舞
    #include <algorithm>
    #include <string>
    #include <cstring>
    using namespace std;
    const int MaxN = 210;
    
    int n;
    string s[105];
    int dp[MaxN][MaxN];
    
    //dp[i][j] = min{ dp[i - 1][j - 1], dp[i - 1][j + 1] } +2;
    void Print(int n)
    {
        int s = 0;
        for (int i = 1; i <= n; i = i + 2)
            s += i;
        cout << s << endl;
    }
    
    void DP()
    {
        memset(dp, -1, sizeof(dp));
        int maxt = 0;
        for (int i = 1; i <= n; i++)
            for (int j = i - 1; j < (int)s[i].length(); j++)
                if (s[i][j] == '-')
                    dp[i][j + 1] = 1;
    
        //for (int i = 1; i <= n; i++)
        //  cout << s[i] << endl;
    
        for (int i = 1; i <= n; i++)                                            //从上往下, 遍历单号
            for (int j = i; j <= (int)s[i].length(); j = j + 2)
            {
                if (dp[i][j] > 0 && dp[i - 1][j] > 0)
                    dp[i][j] = min(dp[i - 1][j - 1], dp[i - 1][j + 1]) + 2;
                maxt = max(maxt, dp[i][j]);
            }
        
        for (int i = n - 1; i >= 1; i--)                                        //从下往上, 遍历双号
            for (int j = i + 1; j < (int)s[i].length(); j = j + 2)
            {
                if (dp[i][j] > 0 && dp[i + 1][j] > 0)
                    dp[i][j] = min(dp[i + 1][j - 1], dp[i + 1][j + 1]) + 2;
                maxt = max(maxt, dp[i][j]);
            }
    
        Print(maxt);
    }
    
    int main()
    {
        cin >> n;
        getchar();
        for (int i = 1; i <= n; i++)
            getline(cin,s[i]);
    
        DP();
    
        system("pause");
        return 0;
    }
    
  • 1
    @ 2019-09-11 19:54:57

    从倒三角的上方到下方逐行DP,DP时只针对每一个倒立小三角形。
    一旦该倒立小三角形上方的正立小三角型是‘-’,那么就可以与左上的三角形和右上的三角形构成更大的新三角形。这时候取左上和右下的最小值即可。

    #include <bits/stdc++.h>
    
    using namespace std;
    
    int n;
    bool ma[150][300]={0};
    int dp[150][300]={0};
    
    int main()
    {
        cin>>n;
        int i,j,k,ans=0;
        char c;
        fflush(stdin);
        for(i=n;i>0;i--)
        {
            k=n-i;
            for(j=0;j<2*i-1;j++)
            {
                cin>>c;
                if(c=='-')
                {
                    ma[k][j]=true;
                    if(j%2==0)
                    {
                        dp[k][j]=1;
                    }
                }
            }
        }
        for(i=1;i<n;i++)
        {
            for(j=0;j<(n-i)*2-1;j++)
            {
                if(ma[i][j]&&ma[i-1][j+1]&&j%2==0)
                {
                    dp[i][j]=min(dp[i-1][j],dp[i-1][j+2])+1;
                }
                ans=max(ans,dp[i][j]);
            }
        }
        cout<<ans*ans<<endl;
        return 0;
    }
    
  • 1
    @ 2008-09-19 20:04:37

    编译通过...

    ├ 测试数据 01:答案正确... 0ms

    ├ 测试数据 02:答案正确... 0ms

    ├ 测试数据 03:答案正确... 0ms

    ├ 测试数据 04:答案正确... 0ms

    ├ 测试数据 05:答案正确... 0ms

    ├ 测试数据 06:答案正确... 0ms

    ├ 测试数据 07:答案正确... 0ms

    ├ 测试数据 08:答案正确... 0ms

    ├ 测试数据 09:答案正确... 0ms

    ├ 测试数据 10:答案正确... 0ms

    ---|---|---|---|---|---|---|---|-

    Accepted 有效得分:100 有效耗时:0ms

    这很奇怪,我没考虑尖向下的情形,竟然过了,讨论里有我的程序,仅供参考。

  • 0
    @ 2017-05-29 18:04:52

    Accepted

    状态 耗时 内存占用

    #1 Accepted 3ms 256.0KiB
    #2 Accepted 3ms 352.0KiB
    #3 Accepted 3ms 356.0KiB
    #4 Accepted 3ms 256.0KiB
    #5 Accepted 3ms 384.0KiB
    #6 Accepted 3ms 256.0KiB
    #7 Accepted 3ms 256.0KiB
    #8 Accepted 4ms 476.0KiB
    #9 Accepted 4ms 488.0KiB
    #10 Accepted 4ms 488.0KiB
    代码

    #include<iostream>
    #include<algorithm>
    using namespace std;
    int f[110][210]={0},n,ans=0;
    char c;
    bool a[110][210]={0};
    int main()
    {
        cin>>n;
        for(int i=1;i<=n;i++)
            for(int j=1;j<=2*(n-i)+1;j++)
            {
                cin>>c;
                if(c==' ')
                    j--;
                if(c=='-')
                    a[i][j]=1;
            }
        for(int i=1;i<=n;i++)
            for(int j=1;j<=2*(n-i)+1;j+=2)
            {
                if(a[i][j]==1&&a[i-1][j+1]==0)
                    f[i][j]=1;
                if(a[i][j]==1&&a[i-1][j+1]==1)
                    f[i][j]=min(f[i-1][j],f[i-1][j+2])+1;
                ans=max(ans,f[i][j]);
            }
        for(int i=n;i>=1;i--)
            for(int j=2;j<=2*(n-i);j+=2)
            {
                if(a[i][j]==1&&a[i+1][j-1]==0)
                    f[i][j]=1;
                if(a[i][j]==1&&a[i+1][j-1]==1)
                    f[i][j]=min(f[i+1][j],f[i+1][j+2])+1;
                ans=max(ans,f[i][j]);
            }
        cout<<ans*ans;
        return 0;
    }
    
  • 0
    @ 2016-09-10 23:02:11

    此题细节神tm多啊
    1、三角形向上向下(一开始想到了)
    2、三角形向上向下的方程需要判断j是否为偶数!!(请看题中的图)
    #include <cstdio>
    #include <cstdlib>
    #include <algorithm>
    #define rep(i, x, y) for (int i = x; i <= y; ++i)
    #define dwn(i, x, y) for (int i = x; i >= y; --i)
    using namespace std;

    int n;
    char s[105][205];
    int mp[105][205], l[105][205], f[105][205], g[105][205];

    int main(int argc, const char *argv[]) {
    scanf("%d", &n);
    rep(i, 1, n) scanf("%s", s[i]);
    rep(i, 1, n) rep(j, 0, 2 * (n - i + 1) - 2) {
    mp[i][j + 1] = s[i][j] == '-' ? 1 : 0;
    }
    rep(i, 1, n) rep(j, 1, 2 * (n - i + 1) - 1) {
    if (mp[i][j]) l[i][j] = l[i][j - 1] + 1;
    }
    int ans = 0;
    rep(i, 1, n) {
    rep(j, 1, 2 * (n - i + 1) - 1) {
    if (j % 2 != 0) continue;
    if (mp[i][j] == 1) {
    if (j - 2 <= 0 || mp[i][j - 1] == 0) {f[i][j] = 1; continue;}
    f[i][j] = min(f[i - 1][j - 2], (l[i][j - 2] + 1) / 2) + 1;
    }
    }
    }
    dwn(i, n, 1) {
    rep(j, 1, 2 * (n - i + 1) - 1) {
    if (j % 2 != 1) continue;
    if (mp[i][j] == 1) {
    if (j - 2 <= 0 || mp[i][j - 1] == 0) {g[i][j] = 1; continue;}
    g[i][j] = min(g[i + 1][j - 2], (l[i][j - 2] + 1) / 2) + 1;
    }
    }
    }
    /*
    rep(i, 1, n) {
    rep(j, 1, 2 * (n - i + 1) - 1) {
    printf("%d ", g[i][j]);
    }
    printf("\n");
    }
    */
    rep(i, 1, n) {
    rep(j, 1, 2 * (n - i + 1) - 1) {
    ans = max(ans, max(f[i][j], g[i][j]));
    }
    }
    printf("%d\n", ans * ans);
    return 0;
    }

  • 0
    @ 2013-10-01 17:03:40

    没有一次AC,看了题解才知道,原来要判断奇偶性,

    因为如果三角性先下,定点应该在奇数行
    相反,

    加上这句话就行了

    DXE-SYF

  • 0
    @ 2013-08-18 00:05:01

    #include<cstdio>
    #include<cstring>
    int d[110][220];
    char a[110][220],n,ans;
    int Min(int a,int b,int c){a=a<b?a:b;a=a<c?a:c;return a;}
    int Max(int a,int b){return a>b?a:b;}
    int main()
    {scanf("%d",&n);ans=0;
    for(int i=1;i<=n;i++)
    for(int j=i;j<i+2*n+1-2*i;j++)
    scanf(" %c",&a[i][j]);
    for(int i=1;i<=2*n-1;i++)if(a[1][i]=='-'){d[1][i]=1;ans=1;}
    for(int i=2;i<=n;i++)
    for(int j=i;j<i+2*n+1-2*i;j++)
    if(a[i][j]=='-'&&((i&1)==(j&1)))
    {d[i][j]=1;
    if(a[i-1][j]=='-'&&a[i-1][j-1]=='-'&&a[i-1][j+1]=='-')
    d[i][j]=Min(d[i-1][j-1]+1,d[i-1][j+1]+1,d[i-2][j]+2);

    ans=Max(ans,d[i][j]);

    }
    printf("%d\n",ans*ans);
    }

  • 0
    @ 2013-07-01 14:26:59

    odd隐藏得够深的。。又被骗到了

  • 0
    @ 2013-03-13 23:10:48

    我用盖房子的思路过了。但交了8次啊,主要是细节问题太多了,烦死我了!
    上次40分的程序我知道哪里错了,就是斜着的边不一定是能构造了,中间可能断开,不能直接2*n-1

  • 0
    @ 2013-03-01 18:27:39

    哪位大牛帮我看下,我用盖房子的思路的。只有40分,气死了!检查不出来!F[I,J]表示朝下的那个点的最大变长;G相反。
    var ans,n,m,i,j,k,w,max,t,x,h,y:longint;
    f,g:array[-3..110,-3..210]of longint;
    a:array[-3..110,-3..210]of char;
    s:string;
    function min(a,b:longint):longint;
    begin
    if a>b then exit(b)
    else exit(a);
    end;
    begin
    readln(n);
    for i:=1 to n do begin
    readln(s);
    for j:=1 to n*2-1 do begin
    a[i,j]:=s[j];
    if a[i,j]='-'then begin
    f[i,j]:=1;
    g[i,j]:=1;
    end;
    end;
    end;
    for i:=n downto 1 do
    for j:=1 to n*2-1 do begin
    x:=i;y:=j;w:=0;t:=0;
    while a[x,y]='-' do begin
    w:=w+1;
    y:=y-1;
    end;
    y:=j;
    while a[x,y]='-' do begin
    t:=t+1;
    x:=x+1;
    y:=y-1;
    end;
    t:=t+t-1;
    if (a[i,j]='-') then
    if odd(i) then begin
    if odd(j) then begin
    if (a[i+1,j-3]='-') then h:=min(min(w,t),f[i+1,j-3]+4)
    else if min(w,t)>=3 then h:=3;
    if (h=w)and(not(odd(w)))then
    f[i,j]:=h-1
    else f[i,j]:=h;
    end;
    end
    else if not(odd(j)) then begin
    if (a[i+1,j-3]='-') then h:=min(min(w,t),f[i+1,j-3]+4)
    else if min(w,t)>=3 then h:=3;
    if (h=w)and(not(odd(w)))then
    f[i,j]:=h-1
    else f[i,j]:=h;
    end;
    end;
    for i:=1 to n do
    for j:=1 to n*2-1 do begin
    x:=i;y:=j;w:=0;t:=0;
    while a[x,y]='-' do begin
    w:=w+1;
    y:=y-1;
    end;
    y:=j;
    while a[x,y]='-' do begin
    t:=t+1;
    x:=x-1;
    y:=y-1;
    end;
    t:=t+t-1;
    if a[i,j]='-' then
    if odd(i) then begin
    if not(odd(j)) then begin
    if (a[i-1,j-3]='-') then h:=min(min(w,t),g[i-1,j-3]+4)
    else if min(w,t)>=3 then h:=3;
    if (h=w)and(not(odd(w)))then
    g[i,j]:=h-1
    else g[i,j]:=h;

    end;
    end
    else if odd(j) then begin
    if (a[i-1,j-3]='-')then h:=min(min(w,t),g[i-1,j-3]+4)
    else if (min(w,t)>=3) then h:=3;
    if (h=w)and(not(odd(w)))
    then g[i,j]:=h-1
    else g[i,j]:=h;
    end;
    end;ans:=0;
    for i:=1 to n do
    for j:=1 to 2*n-1 do begin
    if g[i,j]>ans then ans:=g[i,j];
    if f[i,j]>ans then ans:=f[i,j];
    end;max:=0;
    for i:=1 to ans do if odd(i) then max:=max+i;
    writeln(max);
    end.

  • 0
    @ 2012-10-27 16:27:08

    VijosNT Mini 2.0.5.7 Special for Vijos 

    foo.pas(30,57) Warning: Variable "f" does not seem to be initialized 

    ├ 测试数据 01:答案正确... (0ms, 1492KB) 

    ├ 测试数据 02:答案正确... (0ms, 1492KB) 

    ├ 测试数据 03:答案正确... (0ms, 1492KB) 

    ├ 测试数据 04:答案正确... (0ms, 1492KB) 

    ├ 测试数据 05:答案正确... (0ms, 1492KB) 

    ├ 测试数据 06:答案正确... (0ms, 1492KB) 

    ├ 测试数据 07:答案正确... (0ms, 1492KB) 

    ├ 测试数据 08:答案正确... (0ms, 1492KB) 

    ├ 测试数据 09:答案正确... (0ms, 1492KB) 

    ├ 测试数据 10:答案正确... (0ms, 1492KB) 

    ---|---|---|---|---|---|---|---|-

    Accepted / 100 / 0ms / 1492KB 

    这么水的题交了好几遍才过。。。

    提醒大家一下:

    1:n=100 但第一行会有199个符号

    2:数据中有空格,可以加一个while循环读

    判断奇偶,正反分别递推一遍就可以了

  • 0
    @ 2012-10-13 20:04:09

    一开始写了个预处理的动归,先预处理出某个点左右连续的‘-’有多少,然后进行转移,过八个,后来发现,这么做有一点点后效性,再做,不就是跟那个最大矩阵差不多嘛

    F:=MAX(F,F+1 这是倒着的三角形,正着的同理

    ,我是倒序输入的

    注意奇偶判断,为什么,看看图就知道了

  • 0
    @ 2012-10-09 17:30:13

    补成矩形就好了嘛 f:=min(f,f,f)+1;

    kuso还要加就判断 就是 if odd(i+j-1) then ans:=max(ans,f);

    真恶心··

  • 0
    @ 2012-08-14 08:51:15

    编译通过...

    ├ 测试数据 01:答案正确... (0ms, 660KB)

    ├ 测试数据 02:答案正确... (0ms, 660KB)

    ├ 测试数据 03:答案正确... (0ms, 660KB)

    ├ 测试数据 04:答案正确... (9ms, 660KB)

    ├ 测试数据 05:答案正确... (0ms, 660KB)

    ├ 测试数据 06:答案正确... (0ms, 660KB)

    ├ 测试数据 07:答案正确... (0ms, 660KB)

    ├ 测试数据 08:答案正确... (0ms, 660KB)

    ├ 测试数据 09:答案正确... (0ms, 660KB)

    ├ 测试数据 10:答案正确... (0ms, 660KB)

    不看题解不知道,一看吓一跳 。。 通过数据范围卡人 实在有点恶。。 囧!

  • 0
    @ 2012-07-23 18:18:07

    恶心到让人吐血的DP题。。

    和盖房子那题的思路是一样的:假设T(i,j,k)是以(i,j)为右下角构成的一个k层的**尖端朝下**的三角形。。那么。。若T(i,j,k)成立。。必然有T(i-1,j-2,k-1)成立。。但是仅有其成立是不够的。。因为最底下的一排还没有任何保障。。所以我们应该判断T(i,j-1,k-1)与T(i,j-2,k-1)是否成立。。之所以只判断T(i,j-1,k-1)与T(i,j-2,k-1)是因为

  • 0
    @ 2010-03-18 13:41:42

    编译通过...

    ├ 测试数据 01:答案正确... 0ms

    ├ 测试数据 02:答案正确... 0ms

    ├ 测试数据 03:答案正确... 0ms

    ├ 测试数据 04:答案错误... ├ 标准行输出 9

     ├ 错误行输出 16

    ├ 测试数据 05:答案正确... 0ms

    ├ 测试数据 06:答案正确... 0ms

    ├ 测试数据 07:答案正确... 0ms

    ├ 测试数据 08:答案正确... 0ms

    ├ 测试数据 09:答案正确... 0ms

    ├ 测试数据 10:答案正确... 0ms

    ---|---|---|---|---|---|---|---|-

    神牛帮帮手啊!过不了第3个额

    说说思路:

    类似于p1057 盖房子

    要搜2次,1次搜向上边长最长的三角形,1次搜向下边长最长的三角形

    #-##---|-#

    ---|--#-

    ---|#-

    -#-

    • -#-
      ---|#-
      ---|--#-
      #-##---|-#
      倒过来看图,你会发现
      向上边长最长的三角形
      当map不为‘-’时,F=0;
      当MAP不为‘-’,当map为‘-’时,F=1;
      当MAP为‘-’,当map为‘-’时,则考虑
      有f:=min(f,f)+1
      ---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
      向下边长最长的三角形
      套用上面就好拉!
      当map不为‘-’时,F=0;
      当MAP不为‘-’,当map为‘-’时,F=1;
      当MAP为‘-’,当map为‘-’时,则考虑
      有f:=min(f,f)+1;

    最后记得把最长的边长平方下即为个数!

  • 0
    @ 2009-11-13 16:05:50

    编译通过...

    ├ 测试数据 01:答案正确... 0ms

    ├ 测试数据 02:答案正确... 0ms

    ├ 测试数据 03:答案正确... 0ms

    ├ 测试数据 04:答案正确... 0ms

    ├ 测试数据 05:答案正确... 0ms

    ├ 测试数据 06:答案正确... 0ms

    ├ 测试数据 07:答案正确... 0ms

    ├ 测试数据 08:答案正确... 0ms

    ├ 测试数据 09:答案正确... 0ms

    ├ 测试数据 10:答案正确... 0ms

    ---|---|---|---|---|---|---|---|-

    Accepted 有效得分:100 有效耗时:0ms

信息

ID
1063
难度
6
分类
动态规划 点击显示
标签
递交数
3388
已通过
825
通过率
24%
被复制
4
上传者