極大化思想的應(yīng)用！
用l，r分別記錄了之前的狀態(tài)！
下一次查找的時候只需要o(1)的時間，最壞情況下是o(n),不過由于壞點很稀疏，最壞情況很少發(fā)生！
所以程序非常快！
Test 1: TEST OK [0.000 secs, 11544 KB]
Test 2: TEST OK [0.011 secs, 11544 KB]
Test 3: TEST OK [0.011 secs, 11544 KB]
Test 4: TEST OK [0.011 secs, 11544 KB]
Test 5: TEST OK [0.011 secs, 11544 KB]
Test 6: TEST OK [0.022 secs, 11540 KB]
Test 7: TEST OK [0.054 secs, 11544 KB]
Test 8: TEST OK [0.194 secs, 11544 KB]
Test 9: TEST OK [0.302 secs, 11540 KB]
Test 10: TEST OK [0.281 secs, 11544 KB]
1 動態(tài)規(guī)劃
2 小炫耀一下
3 程序運行的非常快么！
4 /*
5 ID: hongfei5
6 PROG: rectbarn
7 LANG: C++
8 */
9 #include<iostream>
10 using namespace std;
11 bool map[3001][3001];
12 int h[3001],l[3001],r[3001];
13 int n,m,p;
14 int main()
15 {
16 freopen("rectbarn.in","r",stdin);
17 freopen("rectbarn.out","w",stdout);
18 scanf("%d%d%d",&n,&m,&p);
19 int a,b;
20 for(int i=0;i<p;++i)
21 {
22 scanf("%d%d",&a,&b);
23 map[a][b]=1;//1表示是壞點
24 }
25 h[0]=0;
26 int Max=0;
27 //[i,j]為(i,h[i,j])這條線段向左邊擴展的最長距離，r[i,j]為(i,h[i,j])向右邊擴展的最長距離
28 for(int i=1;i<=n;++i)
29 {
30 l[i]=0;
31 r[i]=m+1;
32 for(int j=1;j<=m;++j)
33 if(map[i][j])
34 {
35 r[i]=j;
36 break;
37 }
38 }
39 for(int j=1;j<=m;++j)
40 {
41 int len_l=INT_MAX;
42 int len_r=INT_MAX;
43 for(int i=1;i<=n;++i)
44 {
45 if(map[i][j])
46 {
47 l[i]=j;
48 h[i]=0;
49 r[i]=m+1;
50 len_l=len_r=INT_MAX;
51 for(int k=j+1;k<=m;++k)
52 if(map[i][k])
53 {
54 r[i]=k;
55 break;
56 }
57 }
58 else
59 {
60 h[i]=h[i-1]+1;
61 len_l=min(len_l,j-l[i]);
62 len_r=min(len_r,r[i]-j);
63 int s=(len_l+len_r-1)*h[i];
64 if(s>Max)Max=s;
65 }
66 }
67 }
68 printf("%d\n",Max);
69 return 0;
70 }