洛谷 1736 创意吃鱼法

　　传送门

最开始想到的枚举： 　　

　　其实最开始想错了一些地方，或者说一些地方没有想清楚。

　　现在说一下改完之后的：

　　按行和列枚举点

　　第三层循环有两个 分别是鱼的对角线是从左上到右下 和 从左下到右上

　　枚举的点分别是正方形的左上角点和右上角点

　　分开来循环只有一个目的：方便剪枝

　　举个栗子：
　　4 6
　　0 1 0 1 0 0            我们现在枚举到（1, 2） 这个点
　　0 0 1 0 1 0　　　 鱼在左上到右下的对角线的情况
　　1 1 0 0 0 1　　　 枚举到正方形边长到3的时候就发现不行了
　　0 1 1 0 1 0　　　 这时直接break 因为边长为4的情况肯定不行了

　　要注意很多细节啊 调了挺久的

 1 #include<iostream>
 2 #include<cstdio>
 3 #define go(i,a,b) for(register int i=a;i<=b;i++)
 4 #define M 2510
 5 using namespace std;
 6 int read()
 7 {
 8     int x=0,y=1;char c=getchar();
 9     while(c<‘0‘||c>‘9‘) {if(c==‘-‘) y=-1;c=getchar();}
10     while(c>=‘0‘&&c<=‘9‘) {x=(x<<1)+(x<<3)+c-‘0‘;c=getchar();}
11     return x*y;
12 }
13 int n,m,ans=1;
14 bool mp[M][M],f1=0;
15 bool ck1(int x,int y,int k)      
16 {
17     go(i,x,x+k) go(j,y,y+k)
18     {
19         if(i-x==j-y && !mp[i][j]) return 0;
20         if(i-x!=j-y && mp[i][j]) return 0;
21     }
22     return 1;
23 }
24 bool ck2(int x,int y,int k)
25 {
26     int z=x+y;
27     go(i,x,x+k) go(j,y-k,y)
28     {
29         if(i+j==z && !mp[i][j]) return 0;
30         if(i+j!=z && mp[i][j]) return 0;
31     }
32     return 1;
33 }
34 int main()
35 {
36     n=read();m=read();
37     go(i,1,n) go(j,1,m) {mp[i][j]=read();if(mp[i][j]) f1=1;}
38     if(!f1) {puts("0");return 0;}
39     go(i,1,n) go(j,1,m)
40     {
41         int maxn=min(n-i+1,m-j+1);
42         go(k,ans+1,maxn)
43         {
44             if(ck1(i,j,k-1)) ans=k;
45             else break ;
46         }
47         maxn=min(n-i+1,j);
48         go(k,ans+1,maxn)
49         {
50             if(ck2(i,j,k-1)) ans=k;
51             else break ;
52         }
53     }
54     printf("%d",ans);
55     return 0;
56 }

枚举 View Code

　　本来以为会TLE几个点 结果 猝不及防地AC了？？

　　不过挺慢的 2024ms 开O2 964ms

小结：   在打代码之前再理一理思路 从头到尾想一遍（毕竟我总是没想清楚而错）

然后又去想 DP:

　　感觉好像已经挺明显的了 明天再写吧！！

洛谷 1736 创意吃鱼法

原文：https://www.cnblogs.com/forward777/p/10328360.html