传纸条 Day 1
题目大意：
在 m * n 的矩阵中， 从 (1,1) 到 (m, n) 的两条路劲和最大， 并且不相交
解法一：
其实是一个很简单的棋盘形dp，可以直接看成 (1,1) 到 (m, n) 的两条严格不相交路劲。
直接思维DP，设f[i][j][k][l]为从第一张纸条到达 (i, j) ，第二张纸条 (k,l) 的路径上取得的最大的好心程度和。
那么特别显然，转移方程是 f[i][j][k][l]=max( f[i][j-1][k-1][l] , f[i-1][j][k][l-1] , f[i][j-1][k][l-1] , f[i-1][j][k-1][l] )+a[i][j]+a[k][l]。
要小心l的枚举范围，应该是从j+1到m，只有这样，在枚举第二条路的时候可以控制下标的l不会和j有相等的可能，这样可以保证两条路一定不相交
由于终点的值是0，所以目标状态就是f[n][m-1][n-1][m]。
如果你不想这样做，那就让l直接从1枚举，但需要加一个判断，判断当前的(i,j)和(k,l)是不是重合了，如果重合那就把f数组对应的这个地方在转移后减掉一个a[i][j]或者a[k][l]。
时间复杂度就是 O(m * m * n * n)
Code block
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
| #include <iostream>
#include <cstdio>
#include <cmath>
using namespace std;
const int N = 55;
int f[N][N][N][N];
int a[N][N];
int n, m;
int Max(int a, int b, int c, int d){
if(a < b) a = b;
if(a < c) a = c;
if(a < d) a = d;
return a;
}
int main(){
scanf("%d%d", &m, &n);
for(int i = 1; i <= m; i++){
for(int j = 1; j <= n; j++){
scanf("%d", &a[i][j]);
}
}
for(int i = 1; i <= m; i++){
for(int j = 1; j <= n; j++){
for(int l = 1; l <= m; l++){
for(int r = j + 1; r <= n; r++){
f[i][j][l][r] = Max(f[i-1][j][l-1][r],f[i][j-1][l][r-1],f[i][j-1][l-1][r],f[i-1][j][l][r-1]);
f[i][j][l][r] += a[i][j] + a[l][r];
}
}
}
}
printf("%d\n", f[m][n-1][m-1][n]);
return 0;
}
|
解法二：
简化到三维，因为 i + j == l + k == Step
那么可以用f[k][i][j]记录最大值
转移式 f[k][i][j] = Max(f[k-1][i-1][j], f[k-1][i-1][j-1], f[k-1][i][j], f[k-1][i][j-1])
目标 f[n+m-1][m][m]
第一维度维护的是在传的过程中纵坐标与横坐标的和。
第二维度维护的是第一张纸条的点的纵坐标。
第三维度维护的是第二张纸条的点的纵坐标。
让第一张纸相对于第二张靠右。
时间复杂度 O(m * n * (m + n) )
Code block
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
| #include <iostream>
#include <cstdio>
#include <cmath>
using namespace std;
const int N = 55;
int f[N*2][N][N];
int a[N][N];
int n, m;
int Max(int a, int b, int c, int d){
if(a < b) a = b;
if(a < c) a = c;
if(a < d) a = d;
return a;
}
int main(){
scanf("%d%d", &m, &n);
for(int i = 1; i <= m; i++){
for(int j = 1; j <= n; j++){
scanf("%d", &a[i][j]);
}
}
for(int k = 1; k < n + m; k++){
for(int i = 1; i <= m; i++){
for(int j = 1; j <= m; j++){
if(k < i || k < j) continue;
f[k][i][j] = Max(f[k-1][i-1][j], f[k-1][i-1][j-1], f[k-1][i][j], f[k-1][i][j-1]);
f[k][i][j] += a[i][k-i+1] + a[j][k-j+1];
if(i == j) f[k][i][j] -= a[i][k-i+1];
}
}
}
printf("%d\n", f[n+m-1][m][m]);
return 0;
}
|
解法三：
之前在 POJ 上写过一题会 MTL 的， 可以优化第一维， 因为第一维只会从他前面一个状态
转移，即 f[k] 只会从 f[k-1] 来，那么第一维只要开个 2 就行了
传送门POJ // 有空补一下题解， 蛮有意思的环形处理
Code block
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
| #include <iostream>
#include <cstdio>
#include <cmath>
using namespace std;
const int N = 55;
int f[2][N][N];
int a[N][N];
int n, m;
int Max(int a, int b, int c, int d){
if(a < b) a = b;
if(a < c) a = c;
if(a < d) a = d;
return a;
}
int main(){
scanf("%d%d", &m, &n);
for(int i = 1; i <= m; i++){
for(int j = 1; j <= n; j++){
scanf("%d", &a[i][j]);
}
}
for(int k = 1; k < n + m; k++){
for(int i = 1; i <= m; i++){
for(int j = 1; j <= m; j++){
if(k < i || k < j) continue;
f[k&1][i][j] = Max(f[(k-1)&1][i-1][j], f[(k-1)&1][i-1][j-1], f[(k-1)&1][i][j], f[(k-1)&1][i][j-1]);
f[k&1][i][j] += a[i][k-i+1] + a[j][k-j+1];
if(i == j) f[k&1][i][j] -= a[i][k-i+1];
}
}
}
printf("%d\n", f[(n+m-1)&1][m][m]);
return 0;
}
|
