1 import java.io.*;
2 import java.util.*;
3
4 /*
5 ID: yanglei4
6 LANG: JAVA
7 TASK:bigbrn
8 */
9 public class bigbrn {
10 public static int min(int a, int b) {
11 if (a < b) return a;
12 else return b;
13 }
14 public static int min3(int a, int b, int c) {
15 return min(a, min(b, c));
16 }
17 public static void main(String[] args) throws IOException {
18 BufferedReader f = new BufferedReader(new FileReader("bigbrn.in"));
19 PrintWriter out = new PrintWriter(new BufferedWriter(new FileWriter("bigbrn.out")));
20 StringTokenizer st = new StringTokenizer(f.readLine());
21 int N = Integer.parseInt(st.nextToken());
22 int T = Integer.parseInt(st.nextToken());
23 int[][] map = new int[N][N];
24 for (int i = 0; i < T; i++) {
25 st = new StringTokenizer(f.readLine());
26 int x = Integer.parseInt(st.nextToken());
27 int y = Integer.parseInt(st.nextToken());
28 map[x - 1][y - 1] = -1;
29 }
30
31 for (int i = 0; i < N; i++) {
32 if (map[0][i]!= -1)
33 map[0][i] = 1;
34 if (map[i][0]!= -1)
35 map[i][0] = 1;
36 }
37
38
39 for (int i = 1; i < N; i++)
40 for (int j = 1; j < N; j++) {
41 if (map[i][j] != -1) {
42 int temp = min3(map[i - 1][j], map[i][j - 1], map[i - 1][j - 1]);
43 if (temp != -1) map[i][j] = temp + 1;
44 else map[i][j] = 1;
45 }
46 }
47
48 int max = 0;
49 for (int i = 0; i < N; i++)
50 for (int j = 0; j < N; j++)
51 if (map[i][j] != 0 && map[i][j] > max)
52 max = map[i][j];
53
54 out.println(max);
55 out.close();
56 System.exit(0);
57 }
58 }
59
应该算是一个比较基本的DP吧,状态转移方程也不难想,但是我最开始写成了N^3的了
首先就是用Map[i][j]来表示以i,j为右下角的最大的square的大小
初始化就是第一行,第一列,如果不是#,那么肯定是1
然后对于i,j,我们需要观察i - 1,j - 1,因为是square,所以只跟这个有关
如果在第i行,第j列上面,从当前位置开始,连续map[i-1][j-1]个位置,没有#的话,那么map[i][j] = map[i-1][j-1]+1
我就是在判断连续map[i-1][j-1]这个地方出了问题,我又加了一层循环,所以就变成了N^3的了,然后果然TLE了
这个地方完全没必要用循环一个一个去判断,因为其实你已经有结果了,这个结果就是map[i-1][j]和map[i][j-1]里面小的那个
map[i-1][j]肯定就是从当前位置开始,在第j列上,向上最多可以走多少步不碰到#
因为这时候实际上你已经确定了,#只有可能出现在第i行,第j列上,因为map[i-1][j-1]不是#就保证了这一点
于是,找到两个方向上走的比较近的那个数,如果这个数是小于map[i-1][j-1]的,那么map[i][j]就等于这个数
否则,map[i][j] = map[i-1][j-1]+1
这个地方的重点就是,如果map[i-1][j-1]不是#,那么就保证了#只能在第i行,第j列上面。
只需要检查这两个就可以
然后我们就可以来看map[i-1][j],map[i][j-1],这两个东西其实跟map[i-1][j-1]共享了上面的一块。
如果在第i行,第j列上面出现了#,那么map[i-1][j],map[i][j-1]肯定比map[i-1][j-1]小
否则,我们的square最大也就只能是map[i-1][j-1]+1,因为map[i-1][j-1]已经是以i-1,j-1为右下角最大的square了
于是状态转移方程就是
map[i][j] = min (map[i-1][j],map[i][j-1],map[i-1][j-1]) + 1, map[i][j] != '#'