题目:
蒜国地域是一个 n 行 m 列的矩阵,下标均从 1 开始。蒜国有个美丽的城堡,在坐标 (n,m) 上,蒜头君在坐标 (1,1) 的位置上。蒜头君打算出发去城堡游玩,游玩结束后返回到起点。在出发去城堡的路上,蒜头君只会选择往下或者往右走,而在返回的路上,蒜头君只会选择往上或者往左走,每次只能走一格。已知每个格子上都有一定数量的蒜味可乐,每个格子至多经过一次。 现在蒜头君请你来帮他计算一下,如何计划来回行程,可以收集到最多的蒜味可乐。输入格式
第一行输入两个整数 n,m(1≤n,m≤50),表示蒜国是一个 n 行 m 列的矩阵。 接下来输入 n 行,每行输入 m 个整数,代表一个 n×m 的矩阵,每个整数代表对应位置上的蒜味可乐数量,每行的每两个整数之间用一个空格隔开。其中蒜头君的位置和城堡的位置上没有蒜味可乐,用 0 表示,其余位置上的整数范围在 [1,100] 内。输出格式
输出一行,输出一个整数,表示蒜头君在来回路上能收集到的蒜味可乐的最大值。样例输入
3 3 0 2 9 4 8 6 2 7 0样例输出
36分析:
从起点走到终点,再从终点走回起点(要求两次走的路不可以相交)可以看作两个人一起从起点走到终点,走的过程中不相遇,同时可以把两者位置合并到一个个状态转移方程:dp[i][j][k][l]=max(max(dp[i-1][j][k-1][l],dp[i][j-1][k][l-1]) max(dp[i-1][j][k][l-1],dp[i][j-1][k-1][l])) + mapp[i][j] + mapp[k][l];设为第一个人走到位置为(i,j),第二个人走的位置为(k,l),因为两条路径的当前总步数一样,所以i+j=k+l,将时间复杂度所以为n^3,由因为每个点只能走一次故(i!=k&&j!=l).
代码:
1 #include <map> 2 #include <set> 3 #include <stack> 4 #include <queue> 5 #include <cmath> 6 #include <ctime> 7 #include <string> 8 #include <limits> 9 #include <cstdio> 10 #include <vector> 11 #include <iomanip> 12 #include <cstdlib> 13 #include <cstring> 14 #include <iostream> 15 #include <algorithm> 16 #define Scc(c) scanf("%c",&c) 17 #define Scs(s) scanf("%s",s) 18 #define Sci(x) scanf("%d",&x) 19 #define Sci2(x, y) scanf("%d%d",&x,&y) 20 #define Sci3(x, y, z) scanf("%d%d%d",&x,&y,&z) 21 #define Scl(x) scanf("%I64d",&x) 22 #define Scl2(x, y) scanf("%I64d%I64d",&x,&y) 23 #define Scl3(x, y, z) scanf("%I64d%I64d%I64d",&x,&y,&z) 24 #define Pri(x) printf("%d\n",x) 25 #define Prl(x) printf("%I64d\n",x) 26 #define Prc(c) printf("%c\n",c) 27 #define Prs(s) printf("%s\n",s) 28 #define For(i,x,y) for(int i=x;i<y;i++) 29 #define For_(i,x,y) for(int i=x;i<=y;i++) 30 #define FFor(i,x,y) for(int i=x;i>y;i--) 31 #define FFor_(i,x,y) for(int i=x;i>=y;i--) 32 #define Mem(f, x) memset(f,x,sizeof(f)) 33 #define LL long long 34 #define ULL unsigned long long 35 #define MAXSIZE 55 36 #define INF 0x3f3f3f3f 37 38 const int mod=1e9+7; 39 const double PI = acos(-1.0); 40 41 using namespace std; 42 int dp[MAXSIZE][MAXSIZE][MAXSIZE][MAXSIZE]; 43 int main() 44 { 45 46 Mem(dp,0); 47 int mapp[MAXSIZE][MAXSIZE]; 48 int n,m; 49 Sci2(n,m); 50 For_(i,1,n) 51 For_(j,1,m) 52 Sci(mapp[i][j]); 53 For_(i,1,n) 54 For_(j,1,m) 55 For_(k,1,n) 56 For_(l,1,m) 57 { 58 if(i+j==k+l&&i!=k&&j!=l) 59 { 60 dp[i][j][k][l]=max( max(dp[i-1][j][k-1][l],dp[i][j-1][k][l-1] ),max(dp[i-1][j][k][l-1],dp[i][j-1][k-1][l]))+mapp[i][j]+mapp[k][l];//计算两条路之和,所以这里加上 mapp[i][j]、mapp[k][l] 61 } 62 } 63 Pri(dp[n][m-1][n-1][m]); 64 return 0; 65 }View Code
动态规划真是。。。。。。