洛谷 P1006 传纸条

题目传送门

解题思路:

本题要找两条路径,转换一下,其实就是从左上角开始找两条不相交的最大路径.

用f[i][j][k][l]表示两条路径分别走到(i,j)和(k,l)的时候的最大值.

代码:

 1 #include<cstdio>
 2 #include<iostream>
 3 
 4 using namespace std;
 5 
 6 int n,m,a[51][54],f[51][51][51][51]; 
 7 
 8 int main()
 9 {
10     scanf("%d%d",&m,&n);
11     for(int i = 1;i <= m; i++)
12         for(int j = 1;j <= n; j++)
13             scanf("%d",&a[i][j]);
14     f[0][0][0][0] = 0;
15     for(int i = 1;i <= m; i++)
16         for(int j = 1;j <= n; j++)
17             for(int k = 1;k <= m; k++)
18                 for(int l = j + 1;l <= n; l++)
19                     f[i][j][k][l] = max(max(max(f[i-1][j][k-1][l],f[i-1][j][k][l-1]),f[i][j-1][k-1][l]),f[i][j-1][k][l-1]) + a[i][j] + a[k][l];
20     printf("%d",f[m][n-1][m-1][n]);
21     return 0;
22 }

O(n^2*m^2)

然后我们想,四维有点大,就优化一下,用k表示当前走的步数,分别枚举两条路径走到的行数,即可推出列数.

代码:

 1 #include<cstdio>
 2 #include<iostream>
 3 
 4 using namespace std;
 5 
 6 int n,m,a[51][51],f[200][51][51]; 
 7 
 8 int main()
 9 {    
10     scanf("%d%d",&m,&n);
11     for(int i = 1;i <= m; i++)
12         for(int j = 1;j <= n; j++)
13             scanf("%d",&a[i][j]);
14     f[0][0][0] = 0;
15     for(int k = 1;k <= n + m - 1; k++)//步数 
16         for(int i = 1;i <= m; i++)
17             for(int j = 1;j <= m; j++) {
18                 if(k - i + 1 < 1 || k - j + 1 < 1)
19                     continue;
20                 f[k][i][j] = max(max(max(f[k-1][i][j],f[k-1][i-1][j-1]),f[k-1][i-1][j]),f[k-1][i][j-1]) + a[i][k-i+1] + a[j][k-j+1];
21                 if(j == i)    
22                     f[k][i][j] -= a[i][k-i+1];
23             }
24     printf("%d",f[n+m-1][m][m]);        
25     return 0;
26 }

最坏情况:O(n^3)

//NOIP提高2008 T3