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吧，狀態(tài)轉(zhuǎn)移方程也不難想，但是我最開始寫成了N^3的了
首先就是用Map[i][j]來表示以i，j為右下角的最大的square的大小
初始化就是第一行，第一列，如果不是#，那么肯定是1
然后對于i，j，我們需要觀察i - 1，j - 1，因為是square，所以只跟這個有關
如果在第i行，第j列上面，從當前位置開始，連續(xù)map[i-1][j-1]個位置，沒有#的話，那么map[i][j] = map[i-1][j-1]+1
我就是在判斷連續(xù)map[i-1][j-1]這個地方出了問題，我又加了一層循環(huán)，所以就變成了N^3的了，然后果然TLE了
這個地方完全沒必要用循環(huán)一個一個去判斷，因為其實你已經(jīng)有結(jié)果了，這個結(jié)果就是map[i-1][j]和map[i][j-1]里面小的那個
map[i-1][j]肯定就是從當前位置開始，在第j列上，向上最多可以走多少步不碰到#
因為這時候?qū)嶋H上你已經(jīng)確定了，#只有可能出現(xiàn)在第i行，第j列上，因為map[i-1][j-1]不是#就保證了這一點
于是，找到兩個方向上走的比較近的那個數(shù)，如果這個數(shù)是小于map[i-1][j-1]的，那么map[i][j]就等于這個數(shù)
否則，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列上面出現(xiàn)了#，那么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]已經(jīng)是以i-1,j-1為右下角最大的square了
于是狀態(tài)轉(zhuǎn)移方程就是
map[i][j] = min (map[i-1][j],map[i][j-1],map[i-1][j-1]) + 1, map[i][j] != '#'