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

探 寻 宝 藏

时间限制: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博客,因为觉得写的很不错,所以就记录了下来,如果想看原创,请点击这里