本文共 5034 字，大约阅读时间需要 16 分钟。
传纸条
【问题分析】这个题目要求我们在一个给定的矩阵中选择不相交的两条路径（首尾除外，而且必须相交），使得路径上的所有数和最大。【算法描述】这类题目有两种做法，一种是动态规划，一种是最小费流。由于最小费流实现比较复杂，没有什么实际意义，所以不再赘述。由于两条路径的长度相等，可以用f[k][p][q][x][y]表示在前k的长度中，两条路径的结束点分别在(p,q)、(x,y)的最大权值。显然，这个状态是满足无后效性的，因为路径不可以掉头。而且同时也满足最优性原理，因为当前这个状态必然由若干个子状态演变而来。可以写出下面的状态转移方程：f[k][p][q][x][y]=max{f[k-1][p’][q’][x’][y’]}+val[p][q]+val[x][y]这里，val[i][j]表示第i行第j列的数字大小，要求(p,q)与(p’,q’)相邻，(x,y)与(x’,y’)相邻，而且(p’,q’)≠(x’,y’)。状态初始化为f[1][1][1][1][1]=val[1][1]。分析一下算法的复杂度，时间复杂度为O(n3)，空间复杂度为O(n5)。由于n≤50，使得使用的空间最大可以达到1.2GB，显然是不可以接受的，我们要对其进行优化。一个事实是这样的：如果知道了长度k和横坐标x，那么可以计算出纵坐标y。所以状态可以压缩为f[k][p][x]，这样在空间上就可以接受了。但是记录步数需要2n+1的维度，而2NOIP2008 提高组解题报告 2009-1-4如果知道了坐标，就可以算出步数，所以状态可以更改为f[p][q][x]，这样比刚才优化过的状态少使用了一半的空间。至此，空间上仅仅使用了488KB，可谓优化效果明显。【题目小结】这道题目是2001分区联赛的原题目，在曹老师的《数学建模》讲义中也出现过。就难度而言并不算难题，但是很多人因为内存的问题而丢掉了一道题目的分数。要求我们在审题的时候要注意每一个细节。 dp[x1][y1][x2][y2]=max(dp[x1-1][y1][x2-1][y2],dp[x1-1][y1][x2][y2-1], dp[x1][y1-1][x2-1][y2],dp[x1][y1-1][x2][y2-1])+map[x1][y1]; if(x1!=x2 || y1!=y2) dp[x1][y1][x2][y2] += map[x2][y2];AC代码：
#include开三维数组的方法：#include #include #define MAXN 52using namespace std;int dp[MAXN][MAXN][MAXN][MAXN],map[MAXN][MAXN];int Max(int a,int b){ return a>b?a:b;}int max(int a,int b,int c,int d){ int t1=Max(a,b); int t2=Max(c,d); return Max(t1,t2);}int main(){ freopen("input.txt","r",stdin); int m,n,i,j,x1,y1,x2,y2; while(scanf("%d %d",&m,&n)!=EOF){ for(i=1; i<=m; ++i){ for(j=1; j<=n; ++j) scanf("%d",&map[i][j]); } memset(dp,0,sizeof(dp)); for(x1=1; x1<=m; ++x1){ for(y1=1; y1<=n; ++y1){ for(x2=1; x2<=m; ++x2){ for(y2=1; y2<=n; ++y2){ dp[x1][y1][x2][y2]=max(dp[x1-1][y1][x2-1][y2],dp[x1-1][y1][x2][y2-1], dp[x1][y1-1][x2-1][y2],dp[x1][y1-1][x2][y2-1])+map[x1][y1]; if(x1!=x2 || y1!=y2) dp[x1][y1][x2][y2] += map[x2][y2]; } } } } printf("%d\n",dp[m][n][m][n]); } return 0;}
由于只能走右或下，所以坐标满足x+y=k。这样就能降低维数为3维，方程(核心代码)：
// 核心代码 dp[k][x1][x2]=max(dp[k-1][x1][x2],dp[k-1][x1-1][x2-1], dp[k-1][x1-1][x2],dp[k-1][x1][x2-1])+map[x1][y1]; if(x1!=x2 || y1!=y2) dp[k][x1][x2] += map[x2][y2];
AC代码：
#include#include #include #define MAXN 52using namespace std;int dp[MAXN*2+1][MAXN][MAXN],map[MAXN][MAXN];int Max(int a,int b){ return a>b?a:b;}int max(int a,int b,int c,int d){ int t1=Max(a,b); int t2=Max(c,d); return Max(t1,t2);}int main(){// freopen("input.txt","r",stdin); int m,n,i,j,k,x1,y1,x2,y2; while(scanf("%d %d",&m,&n)!=EOF){ for(i=1; i<=m; ++i){ for(j=1; j<=n; ++j) scanf("%d",&map[i][j]); } memset(dp,0,sizeof(dp)); for(k=1; k<=n+m-1; ++k){ for(x1=1; x1<=k; ++x1){ for(x2=1; x2<=k; ++x2){ y1=k+1-x1; y2=k+1-x2; dp[k][x1][x2]=max(dp[k-1][x1][x2],dp[k-1][x1-1][x2-1], dp[k-1][x1-1][x2],dp[k-1][x1][x2-1])+map[x1][y1]; if(x1!=x2 || y1!=y2) dp[k][x1][x2] += map[x2][y2]; } } } printf("%d\n",dp[m+n-1][m-1][m]); } return 0;}
Matrix HDU 2686
和传纸条类似
四维数组方法：
#include#include #include #define MAXN 52using namespace std;int dp[MAXN][MAXN][MAXN][MAXN],map[MAXN][MAXN];int Max(int a,int b){ return a>b?a:b;}int max(int a,int b,int c,int d){ int t1=Max(a,b); int t2=Max(c,d); return Max(t1,t2);}int main(){// freopen("input.txt","r",stdin); int n,i,j,x1,y1,x2,y2; while(scanf("%d",&n)==1){ for(i=1; i<=n; ++i){ for(j=1; j<=n; ++j) scanf("%d",&map[i][j]); } memset(dp,0,sizeof(dp)); for(x1=1; x1<=n; ++x1){ for(y1=1; y1<=n; ++y1){ for(x2=1; x2<=n; ++x2){ for(y2=1; y2<=n; ++y2){ dp[x1][y1][x2][y2]=max(dp[x1-1][y1][x2-1][y2],dp[x1-1][y1][x2][y2-1], dp[x1][y1-1][x2-1][y2],dp[x1][y1-1][x2][y2-1])+map[x1][y1]; if(x1!=x2 || y1!=y2) dp[x1][y1][x2][y2] += map[x2][y2]; } } } } printf("%d\n",dp[n][n][n][n]); } return 0;}
2.三维数组方法：
#include#include #include #define MAXN 32using namespace std;int dp[MAXN*2+1][MAXN][MAXN], map[MAXN][MAXN];int max(int a,int b,int c,int d){ int t1=a>b?a:b; int t2=c>d?c:d; return t1>t2?t1:t2;}int main(){ int n,i,j,k,x1,x2,y1,y2; while(scanf("%d",&n)!=EOF){ for(i=1; i<=n; ++i){ for(j=1; j<=n; ++j) scanf("%d",&map[i][j]); } memset(dp,0,sizeof(dp)); for(k=1; k<=2*n-1; ++k){ for(x1=1; x1<=k; ++x1){ for(x2=1; x2<=k; ++x2){ y1 = k+1-x1; y2 = k+1-x2; dp[k][x1][x2] = max(dp[k-1][x1][x2],dp[k-1][x1-1][x2-1], dp[k-1][x1-1][x2],dp[k-1][x1][x2-1])+map[x1][y1]; if(x1!=x2 || y1!=y2) dp[k][x1][x2] += map[x2][y2]; } } } printf("%d\n",dp[k-1][n-1][n]); } return 0;}
转载地址：http://yuzni.baihongyu.com/