USACO Big Barn

看到这个题目，最先想到的就是使用动态规划了，不过动态规划也要选合适的状态表示法。

本人最初这样表示状态：

用havetree[i][j][l]（实际上只要i，j）表示以（i，j）为左上角，l为边长的正方形内是否有树。

那么转移方程就是

if(havetree[i][j][l] == 1)     havetree[i][j][l + 1] = 1

else if(新扩展的两个边都没有树)             havetree[i][j][l + 1] = 1

最后输出有 havetree[i][j][l]=0的l的最大值即可。

然而，上面的算法只能通过前9个测试点。想到如果在一个正方形的右、下、右下方分别放置同样大小的正方形，可以把边长扩大为2×l。因此，代码中就多了一段Fast expand的过程。

代码如下：

C语言: 高亮代码由发芽网提供

001 #include <stdio.h>
002 #include <stdlib.h>
003 #include <string.h>
004
005 _Bool bak[1001][1001] = {};
006 _Bool havetree[1001][1001] = {};
007 _Bool map[1001][1001] = {};
008 int N,T;
009
010 void init()
011 {
012     int i,j;
013     scanf("%d%d\n",&N,&T);
014     while(T --)
015     {
016         scanf("%d%d\n",&i,&j);
017         map[i - 1][j - 1] = 1;
018     }
019 }
020
021 int check_edge(int i,int j,int l)
022 {
023     int k;
024     for(k = i;k < i + l - 1;k ++)
025     {
026         if(map[k][j + l - 1] == 1)    return 1;
027     }
028     for(k = j;k <= j + l - 1;k ++)
029     {
030         if(map[i + l - 1][k] == 1)    return 1;
031     }
032     return 0;
033 }
034
035 void debug()
036 {
037     int i,j;
038     for(i = 0;i < N;i ++)
039     {
040         for(j = 0;j < N;j ++)    printf("%2d",(int)havetree[i][j]);
041         putchar('\n');
042     }
043 }
044
045 void terminate()
046 {
047     fclose(stdin);
048     fclose(stdout);
049     exit(0);
050 }
051
052 int main()
053 {
054     freopen("bigbrn.in","r",stdin);
055     freopen("bigbrn.out","w",stdout);
056     init();
057     int l,i,j;
058     int success;
059     int max = 0;
060     //max = 0 or 1 exception
061     for(i = 0;i < N;i ++)
062         for(j = 0;j < N;j ++)
063         {
064             if(map[i][j] == 0)    max = 1;
065             havetree[i][j] = map[i][j];
066         }
067     if(max == 0)    {printf("%d\n",max);terminate();}
068     //Fast expand
069     for(l = 2;l <= N;l *= 2)
070     {
071         memcpy(bak,havetree,sizeof(bak));
072         success = 0;
073         for(i = 0;i < N;i ++)
074         {
075             if(i + l - 1>= N)    continue;
076             for(j = 0;j < N;j ++)
077             {
078                 if(j + l - 1 >= N)    continue;
079                 if(havetree[i][j])    continue;
080                 if(havetree[i + (l >> 1)][j] || havetree[i + (l >> 1)][j + (l >> 1)] || havetree[i][j + (l >> 1)])
081                     havetree[i][j] = 1;
082                 else
083                 {
084                     max = l;
085                     success = 1;
086                 }
087             }
088         }
089         if(!success)  //all extensions failed
090         {
091             memcpy(havetree,bak,sizeof(havetree));
092             break;
093         }
094     }
095     fprintf(stderr,"%d\n",max);
096     for(l = max + 1;l <= N;l ++)
097     {
098         success = 0;
099         for(i = 0;i < N;i ++)
100         {
101             if(i + l - 1>= N)    continue;
102             for(j = 0;j < N;j ++)
103             {
104                 if(j + l - 1 >= N)    continue;
105                 if(havetree[i][j])    continue;
106                 if(check_edge(i,j,l))
107                     havetree[i][j] = 1;
108                 else
109                 {
110                     max = l;
111                     success = 1;
112                 }
113             }
114         }
115         if(!success)    break;
116     }
117     //debug();
118     printf("%d\n",max);
119     return 0;
120 }

可是呢，上面的代码只能通过前10个测试点，因为上面的算法在极端情况下会达到n^4的时间规模。于是放弃上面的状态表示法。忍不住看了题解后，采用max[i][j]表示以(i,j)为左上顶点的没有树的正方形的最大边长。

因此有转移方程：
if((i,j)不是树)
    max[i][j] = min(max[i-1][j],max[i][j-1],max[i-1][j-1]) + 1;
顺利通过全部数据。

C语言: 高亮代码由发芽网提供

01 #include <stdio.h>
02 #include <stdlib.h>
03 #include <string.h>
04
05 int max[1002][1002] = {};
06 _Bool map[1002][1002] = {};
07 int N,T;
08
09 void init()
10 {
11     int i,j;
12     scanf("%d%d\n",&N,&T);
13     while(T --)
14     {
15         scanf("%d%d\n",&i,&j);
16         map[i][j] = 1;
17     }
18 }
19
20 void dp()
21 {
22     int i,j;
23     int tmp;
24     for(i = 1;i <= N;i ++)
25         for(j = 1;j <= N;j ++)
26         {
27             if(map[i][j])    max[i][j] = 0;
28             else max[i][j] = 1;
29         }
30     for(i = N;i > 0;i --)
31         for(j = N;j > 0;j --)
32             if(map[i][j] == 0)
33             {
34                 tmp = N + 1;
35                 if(max[i + 1][j] < tmp)    tmp = max[i + 1][j];
36                 if(max[i][j + 1] < tmp)    tmp = max[i][j + 1];
37                 if(max[i + 1][j + 1] < tmp)    tmp = max[i + 1][j + 1];
38                 max[i][j] = tmp + 1;
39             }
40     int ans = 0;
41     for(i = 0;i < N;i ++)
42         for(j = 0;j < N;j ++)
43             if(max[i][j] > ans)    ans = max[i][j];
44     printf("%d\n",ans);
45 }
46
47 int main()
48 {
49     freopen("bigbrn.in","r",stdin);
50     freopen("bigbrn.out","w",stdout);
51     init();
52     dp();
53     fclose(stdout);
54     return 0;
55 }