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] != '#'