综述

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

一维累加和

题目描述:

给定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;
}