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的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。