综述

这几天做了几道特别神奇的题目，让我感受到了算法的真正高效！这几道题的思路就是使劲压，从三维压到二维，从二维到一维，一维再优化，然后就可以将算法的复杂度下降很多很多。具体看下面的题：

一维累加和

题目描述：

给定N个数，求这N(1 <=N <= 100,000) 个数的某个连续子序列的累加和，保证这个连续子序列的累加和最大。

输入：

第一行：一个整数N。(1 <=N <= 100,000) 接下来N行，每行一个整数P_i(-1,000 <= P_i <= 1,000)。表示第i个数。

输出：

一个整数，表示子序列的最大连续累加和。

题解：

这道题首先来说……

单纯的进行一个个枚举然后加到一起最后排序是绝对不行的，因为复杂度是O(N*N*N)，所以说，我们需要进行优化。

因为一个序列是要不停地加下去的，如果前面的序列是正的，那么加到后面肯定变大，而如果是负数，那么还不如不加。于是我们就可以计算累加和，如果前面的累加和是整数，继续加下去，并和maxx（用来记录最大值）比较。如果累加和是负数，清零，然后重新加。最后比较出来的maxx一定就是最大值！

然后O(N)解决！

代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
#include<iostream>
#include<algorithm>
using namespace std;
int main()
{
    ios::sync_with_stdio(false);
    int n,m,maxnum=-20000000;
    long long s=0;
    cin>>n;
    for(int i=1;i<=n;i++)
    {
        cin>>m;
        s+=m;
        if(s>maxnum) maxnum=s;
        if(s<0) s=0;
    }
    cout<<maxnum<<endl;
    return 0;
}

二维累加和(压缩要开始了)

题目描述：

给定一个正整数n（ n<=500），然后输入一个N*N矩阵。求矩阵中最大加权矩形，即矩阵的每一个元素都有一权值，权值定义在整数集上。从中找一矩形，矩形大小无限制，是其中包含的所有元素的和最大 。矩阵的每个元素属于[-1100,1100]

输入：

第一行：n

接下来是n行n列的矩阵。

输出：

一个整数，表示最大子矩阵的和。

题解：

这道题书上有两种优化方法，一种是压缩维度，另一种就是预处理答案然后用公式，但是后者要慢很多慢很多。

具体方法：

第一种方法就是首先预处理出每一个位置 (x，y) 到 (1,1) 这个矩阵的累加和，用 a[i][j]=a[i-1][j]+a[i][j-1]-a[i-1][j-1]+ans (其中ans表示当前 a[i][j] 所在位置的初始值)这个公式的意思可以自己理解。然后我们就用O(N)的复杂度就解决了构建问题。

然后我们只需要再次使用一个公式，就可以求出 (x1,y1) 到 (x2,y2) 这个矩阵的累加和：num=a[x2][y2]-a[x1-1][y2-1]-a[x2][y1-1]+a[x1-1][y1-1] 这个公式就可以很好的求出啦；

再次的，我们使用一个四重循环，枚举每一个可能的矩形，然后计算出累加和，在和maxx比较赋值，最后留下来的答案就是最大的了；

BUT 看题目，数据范围是500 ，四次方呢……62 500 000 000 超时……

好不容易写出来的代码结果不对，妈卖批……

但是还有第二种更快的方法，就需要压缩了，压缩就是将一个求二维的压缩为求一维的方法，首先同样需要预处理，预处理出来这个矩阵中，纵向相加的值，比如在这个预处理的矩阵中 a[i][j] 就代表着，在第 j 列，前 i 行的所有累加和。

那么构建的方法也很简单，a[i][j]=a[i-1][j]+a[i][j] ； 然后我们就可以用 i 坐标相减的方法求出在 j 列，两个 i 坐标之间所有数的累加和，你可能想问，这样也不是有多高效啊，但是看P1173中优化的方法，就知道这个用优先队列找最大连续累加和的效率有多恐怖了。这样，我们只需要用一个二重循环确定这个矩阵的 x1 x2 然后利用一个一维数组 b[i] 存下在确定 x1 x2 的这种情况下，第 i 列的累加和，一个或者多个 b[i] 就构建出来了矩阵。然后由于我们已经压缩成了多个一维，所以参看P1173的优化方法。

O(N*N*N) 完美AC；

代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
#include<iostream>
#include<algorithm>
#include<cstdio>
using namespace std;
int main()
{
    ios::sync_with_stdio(false);
    long long n,ans,num=-200000;
    int a[501][501],b[501][501],c[501];
    cin>>n;
    for(int i=1;i<=n;i++)
        for(int j=1;j<=n;j++)
        {
            if(i==0||j==0)
            {
                a[i][j]=0;
                continue;
            }
            cin>>a[i][j];
            b[i][j]=b[i-1][j]+a[i][j];
        }
    for(int i=1;i<=n;i++)
        for(int j=i;j<=n;j++)
        {
            for(int k=1;k<=n;k++)
                c[k]=b[j][k]-b[i-1][k];
            ans=0;
            for(int k=1;k<=n;k++)
            {
                ans=ans+c[k];
                if(ans>num) num=ans;
                if(ans<0) ans=0;
            }
        }
    cout<<num;
    return 0;
}

三维累加和

题目描述：

我们希望从一个mnh的三维矩阵中,找出一个三维子矩阵,这个子矩阵的权和最大其中对于全部的数据,1<=h<=32,1<=m,n<=50,保证h<=m,n；

输入：

首行三个数h,m,n(注意顺序),分别表示立方体的高,长,宽.

以下h部分,每部分是一个m*n的矩阵,第i部分第j行的第k个数表示立方体第i层,第j行第k列的那块1立方厘米的小正方体的权。

输出:

最大立方体累加和；

题解：

这道题，如果你天真的认为，数据范围不过50多，使劲搞，那真是超时就能超死你了。为什么呢？ O(h*h*h*m*m*m*n*n*n) 大概也就相当于50的9次方吧 2*10^15 超时妥妥的。

但是，我们可以压缩，这道题的思路就是首先将三位压缩为一个一个二维，将二维分别压缩为一维，然后用优先队列的方法求出最大值。思路很简单，看到前两道题应该就能想出来，就是用一个二重循环枚举立方体的h的范围，然后将你所枚举的立方体进行累加和压缩，压缩成一个矩阵，压缩为矩阵之后就像上一道题的方法一样进行计算就好了。

但是刚开始有些绕，所以说建议将图画出来，模拟一下这个压缩的过程，压缩成矩阵后千万不要相信书上的方法，一定要将矩阵再次压缩成线性，不然还是超时，不要问我为什么，我是有亲身经历的。

不过压缩的时候方向也是有讲究的，题目中给出h要比n和m小，所以说我们可以换一个方向压缩，这样就可以优化成 O(h*h*n*m*m) ，这里的换个方向有可能就会在比赛中决定最后一两个数据的AC与否，所以说，能优化的一定要优化。

代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
using namespace std;
int a[100][100][100],b[100][100][100],c[100][100],d[100];
long long maxx=-20000,ans,all;
int main()
{
    ios::sync_with_stdio(false);
    memset(c,0,sizeof(c));
    int h,m,n;
    cin>>h>>m>>n;
    for(int i=0;i<=h;i++)
    for(int j=0;j<=m;j++)
    for(int k=0;k<=n;k++)
    {
        if(i==0||j==0||k==0)
        {
            a[i][j][k]=0;
            b[i][j][k]=0;
            continue;
        }
        cin>>a[i][j][k];
        a[i][j][k]+=a[i-1][j][k];
        b[i][j][k]=a[i][j][k];
    }
    for(int i=1;i<=h;i++)
    for(int j=1;j<=m;j++)
    for(int k=1;k<=n;k++)
    b[i][j][k]=b[i][j][k]+b[i][j][k-1];

    for(int i=1;i<=h;i++)
    for(int j=i;j<=h;j++)
    {
        for(int k=1;k<=m;k++)
		for(int o=1;o<=n;o++)
        {
		    c[k][o]=a[j][k][o]-a[i-1][k][o];
            c[k][o]+=c[k][o-1];
        }

        for(int k=1;k<=n;k++)
		for(int o=k;o<=n;o++)
        {
            for(int x=1;x<=m;x++)
            d[x]=c[x][o]-c[x][k-1];
            ans=0;
            for(int x=1;x<=m;x++)
            {
                ans+=d[x];
                if(ans>maxx) maxx=ans;
                if(ans<0) ans=0;
            }
        }
    }
    cout<<maxx<<endl;
    return 0;
}