生活随笔
收集整理的這篇文章主要介紹了
poj1050 To the Max
小編覺得挺不錯的,現在分享給大家,幫大家做個參考.
真·水題。
我一開始還擔心超時，自己打了個10^8的程序測時間，發現是1.06s左右，心說打個試一下，結果63msA了......
二維前綴和直接暴力枚舉，O(n^4)
1 #include <cstdio>
2 #include <algorithm>
3 using namespace std;
4
5 int main() {
6 int a =
0, b =
0;
7 for(
int i =
1; i <=
10010; i++
) {
8 for(
int j =
1; j <=
10010; j++
) {
9 a = a +
b;
10 b = b +
a;
11 a -=
b;
12 b -=
a;
13 b =
max(a, b);
14 }
15 }
16 printf(
"Hoing Cumor.");
17 return 0;
18 }
測試代碼 1 #include <cstdio>
2 const int N =
103;
3 inline
void max(
int &a,
int b) {
4 if(a < b) a =
b;
5 return;
6 }
7 int a[N][N], sum[N][N];
8
9 inline
void read(
int &
x) {
10 char c =
getchar();
11 bool f =
0;
12 while(c <
'0' || c >
'9') {
13 if(c ==
'-') f =
1;
14 c =
getchar();
15 }
16 while(c >=
'0' && c <=
'9') {
17 x = (x <<
3) + (x <<
1) + c -
'0';
18 c =
getchar();
19 }
20 if(f) x = -
x;
21 return;
22 }
23
24 int main() {
25 int n =
0;
26 read(n);
27 for(
int i =
1; i <= n; i++
) {
28 for(
int j =
1; j <= n; j++
) {
29 read(a[i][j]);
30 sum[i][j] = a[i][j] + sum[i -
1][j] + sum[i][j -
1] - sum[i -
1][j -
1];
31 }
32 }
33 int ans = -
0x7f7f7f7f;
34 for(
int i =
1; i <= n; i++
) {
35 for(
int j =
1; j <= n; j++
) {
36 for(
int ii = i; ii <= n; ii++
) {
37 for(
int jj = j; jj <= n; jj++
) {
38 max(ans, sum[ii][jj] - sum[i -
1][jj] - sum[ii][j -
1] + sum[i -
1][j -
1]);
39 }
40 }
41 }
42 }
43 printf(
"%d", ans);
44 return 0;
45 }
AC代碼 可以看到我瘋狂卡常數......
關于正解，是維度壓縮，把相鄰的數行壓縮為一行然后O(n)求解，時間復雜度O(n^3)
轉載于:https://www.cnblogs.com/huyufeifei/p/9031895.html
總結
以上是生活随笔為你收集整理的poj1050 To the Max的全部內容，希望文章能夠幫你解決所遇到的問題。
如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。
