5

猫粮寸断 LV 10 @ 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

PowderHan LV 10 @ 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

Jong-oo LV 8 @ 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

Lifi LV 10 @ 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

zkkmj LV 8 @ 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

qiuzili LV 8 @ 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

feng_lingsong LV 9 @ 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

S.Y.F LV 10 @ 2013-10-01 17:03:40

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

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

加上这句话就行了

DXE-SYF

1111111129 @ 2014-08-11 20:18:37

orz

0

zy99813 LV 8 @ 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

vcvycy LV 8 @ 2013-07-01 14:26:59

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

0

鲁大牛 LV 7 @ 2013-03-13 23:10:48

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

0

鲁大牛 LV 7 @ 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

SEX丶Elope LV 6 @ 2013-02-16 10:18:26

点击查看程序源码+详细题解

0

Dungeon LV 8 @ 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

silence_sure LV 8 @ 2012-10-13 20:04:09

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

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

，我是倒序输入的

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

0

csw LV 8 @ 2012-10-09 17:30:13

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

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

真恶心··

0

330459659 LV 10 @ 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

nevets LV 7 @ 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

273942569 LV 7 @ 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

gsrq LV 10 @ 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

题解

140 条题解

状态耗时内存占用

-#-

迎春舞会之集体舞

信息

状态

开发

支持

题解

140 条题解

状态 耗时 内存占用

-#-

迎春舞会之集体舞

信息

状态

开发

支持

还没有账户？

登录

状态耗时内存占用