算法

双线程动态规划之探寻宝藏

探 寻 宝 藏

时间限制：1000 ms | 内存限制：65535 KB

难度：5

描述

       传说HMH大沙漠中有一个M*N迷宫，里面藏有许多宝物。某天，Dr.Kong找到了迷宫的地图，他发现迷宫内处处有宝物，最珍贵的宝物就藏在右下角，迷宫的进出口在左上角。当然，迷宫中的通路不是平坦的，到处都是陷阱。Dr.Kong决定让他的机器人卡多去探险。但机器人卡多从左上角走到右下角时，只会向下走或者向右走。从右下角往回走到左上角时，只会向上走或者向左走，而且卡多不走回头路。（即：一个点最多经过一次）。当然卡多顺手也拿走沿路的每个宝物。Dr.Kong希望他的机器人卡多尽量多地带出宝物。请你编写程序，帮助Dr.Kong计算一下，卡多最多能带出多少宝物。

输入

1
2
3
4
第一行： K 表示有多少组测试数据。
接下来对每组测试数据：
第1行: M N
第2~M+1行： Ai1 Ai2 ……AiN (i=1,…..,m)

【约束条件】

1
2
2≤k≤5 1≤M, N≤50 0≤Aij≤100 (i=1,….,M; j=1,…,N)
所有数据都是整数。 数据之间有一个空格。

输出

1
2
3
4
5
对于每组测试数据，输出一行：机器人卡多携带出最多价值的宝物数
样例输入
22 30 10 1010 10 803 30 3 92 8 55 7 100
样例输出
120134

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
#include<iostream>
#include<cstring>
#include<algorithm>
using namespace std;
#define N 52
 int dp[105][N][N],map[N][N];
 int main()
 {
	 int test;
	 cin>>test;
	 while(test--)
	 {
		 int m,n;
		 cin>>m>>n;
		 int i,j;
		 for(i=1;i<=m;++i)
			 for(j=1;j<=n;++j)
				 cin>>map[i][j];

		 memset(dp,0,sizeof(dp));
		 int all=m+n;
		 int k,t1=0,t2=0,ans=0;
		 int x1,y1,x2,y2;

		 dp[2][1][1]=map[1][1];
		 for(k=2;k<=all;++k)
			 for(x1=1;x1<=m;++x1)
				 for(x2=1;x2<=m;++x2)
				{
					y1=k-x1;
					y2=k-x2;
					if(y1<0||y2<0||y1>n||y2>n)
						continue;
					if(y1==y2)
						continue;

					t1=max(dp[k-1][x1-1][x2],dp[k-1][x1-1][x2-1]);
					t2=max(dp[k-1][x1][x2],dp[k-1][x1][x2-1]);
					dp[k][x1][x2]=max(t1,t2)+ map[x1][y1] + map[x2][y2];
				 }
		cout<<dp[all-1][m][m-1]+map[m][n]<<endl;
	 }
	 return 0;
 }


       感觉上面的代码可以直接使用传纸条的代码，只不过最后的输出值直接加上举证左上角的值和右下角的值就好了，具体能不能行得通还有待验证？？？

因为每次只用K,K-1，所以第K步可以换为二维 ，内存少了六倍

优化内存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
#include<iostream>
#include<cstring>
#include<algorithm>
using namespace std;
#define N 52
int dp[2][N][N],map[N][N];
int main()
{
  int test;
  cin>>test;
  while(test--)
  {
    int m,n;
    cin>>m>>n;
    int i,j;
    for(i=1;i<=m;++i)
      for(j=1;j<=n;++j)
        cin>>map[i][j];

    memset(dp,0,sizeof(dp));
    int all=m+n;
    int k,t1=0,t2=0,ans=0;
    int x1,y1,x2,y2;

    dp[2][1][1]=map[1][1];
for(k=2;k<=all;++k)
  for(x1=1;x1<=m;++x1)
    for(x2=1;x2<=m;++x2)
   {
     y1=k-x1;
     y2=k-x2;
     if(y1<0||y2<0||y1>n||y2>n)
       continue;
     if(y1==y2)
       continue;

     t1=max(dp[k%2][x1-1][x2],dp[k%2][x1-1][x2-1]);
     t2=max(dp[k%2][x1][x2],dp[k%2][x1][x2-1]);
     dp[(k+1)%2][x1][x2]=max(t1,t2)+ map[x1][y1] + map[x2][y2];
    }
cout<<dp[(all%2)][m][m-1]+map[m][n]<<endl;
}
return 0;
}

以上内容来自别人的CSDN博客，因为觉得写的很不错，所以就记录了下来，如果想看原创，请点击这里