题解 P1736 【创意吃鱼法】

zhylj · 2017-09-09 12:08:26 · 题解

设f[i][j]为以(i,j)为右下角的最大符合条件正方形

我们发现能吃到的鱼的数量等于边长，所以：

三条绿色直线的长度分别记录为m1,m2,m3（保证绿色的地方都为0，黄色和灰色的地方都为1，m2m3为横，m1为竖线）

那么，在f[i-1][j-1]≥1时，f[i][j]=min{f[i-1][j-1],min{m1,m3}}+1;

f[i][j]=min(f[i-1][j+1],min(m1,m2))+1

在f[i-1][j+1]≥1时，f[i][j]=min{f[i-1][j-1],min{m1,m2}}+1;

（其实本来如果两个都符合还要比个max，但由于数据过水，导致我忽略了这点也可以过）

最后遍历f数组，找最大即可。

核心代码：

    for(int i=1;i<n;i++)
        for(int j=0;j<m;j++)
            if(((j-1>=0&&f[i-1][j-1]>=1)||(j+1<m&&f[i-1][j+1]>=1))&&a[i][j]==1)  //如果符合条件
            {
                m1=0;m2=0;m3=0;  //清零变量
                for(int k=i-1;k>=0&&a[k][j]==0;k--,m1++);  //寻找m1
                for(int k=j+1;k<m&&a[i][k]==0;k++,m2++);  //寻找m2
                for(int k=j-1;k>=0&&a[i][k]==0;k--,m3++);  //寻找m3
                f[i][j]=f[i-1][j-1]>=1? min(f[i-1][j-1],min(m1,m3))+1:min(f[i-1][j+1],min(m1,m2))+1;  //计算
}