动态规划

双线程DP

Posted by zhangmh on 2021-11-19
Estimated Reading Time 8 Minutes
Words 1.8k In Total
Viewed Times

前段时间师哥讲了DP，在练习过程中发现了还有双线程DP，现记录一晚上学习成果：

是看到学校oj上的题 1032 机器人 1460 方格取数 1194 传纸条 1422 传纸条

是看这篇学习的啦 链接戳我

以方格取数为例：

Description

设有N*N的方格图(N< =10),我们将其中的某些方格中填入正整数,而其他的方格中则放入数字0。

某人从图的左上角的A 点(1,1)出发，可以向下行走，也可以向右走，直到到达右下角的B点(N,N)。在走过的路上，他可以取走方格中的数（取走后的方格中将变为数字0）。

此人从A点到B 点共走两次，试找出2条这样的路径，使得取得的数之和为最大。

Input

输入的第一行为一个整数N（表示N*N的方格图），接下来的每行有三个整数，前两个表示位置，第三个数为该位置上所放的数。

一行单独的0表示输入结束。

Output

只需输出一个整数，表示2条路径上取得的最大的和。

走过两遍，路径不重复，取得最大值，是DP问题无疑，从网上查过后才知道是另一种叫双线程DP问题。单线程DP是用二维数组模拟，双线程即可用四维数组模拟，前两维为一路径，后两维为一路经，不分先后。原理同单线程模拟。

下面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
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <stack>
#include <vector>
#include <map>
#include <queue>
#include <cstring>
#include <cmath>
#include <set>
#include <iterator>

using namespace std;

typedef long long ll;
#define ios ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define INF 0x3f3f3f3f
//判断是否需要开ll！！！
//判断是否需要初始化！！！
const int mod=1e9+7;
const int N=15;
int n,x,y,z;
int a[N][N];//记录输入的二维数组，即记录地图 
int f[N][N][N][N];//dp数组，模拟双线程 

int read()
{
	int x=0,f=1;
	char c=getchar();
	while(c<'0'||c>'9')
	{
		if(c=='-')
		f=-1;
		c=getchar();
	}
	while(c>='0'&&c<='9')
	{
		x=x*10+c-'0';
		c=getchar();
	}
	return x*f;
}

int main()
{
//	freopen("test.in","r",stdin);
    n=read();
    while(cin>>x>>y>>z)
    {
    	if(x==0)
    	break;
    	a[x][y]=z;
	}
	for(int i=1;i<=n;i++)
	{
		for(int j=1;j<=n;j++)
		{
			for(int k=1;k<=n;k++)
			{
				for(int l=1;l<=n;l++)
				{
					f[i][j][k][l]+=a[i][j]+a[k][l];
					f[i][j][k][l]+=max(max(f[i-1][j][k-1][l],f[i-1][j][k][l-1]),max(f[i][j-1][k-1][l],f[i][j-1][k][l-1]));
					//两条线路各有两种行走方法，共四种，选择最大的走 
					if(i==k&&j==l)
					f[i][j][k][l]-=a[k][l];
					//两条线路不能走重复的点，若重复，退回 
					//退回时只需退回一步，因两路径并非同时进行，故仅需减 a[k][l]或a[i][j] 均可 
				}
			}
		}
	}
	cout<<f[n][n][n][n]<<'\n';
	return 0;
}

方格取数问题与传纸条很接近啦（甚至还要容易些？），放AC代码，，，稍等，第一遍mle，那有个问题需要注意，数据范围是小于等于50，开的四维数组接近50就可以了，我第一次开的60就mle，，

复习一下开数组的限制范围：

一维：1e6； 二维：3000 ； 三维：没试过； 四维：50~60之间

dbq具体范围不清楚，，，大概就这样

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
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <stack>
#include <vector>
#include <map>
#include <queue>
#include <cstring>
#include <cmath>
#include <set>
#include <iterator>

using namespace std;

typedef long long ll;
#define ios ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define INF 0x3f3f3f3f
//判断是否需要开ll！！！
//判断是否需要初始化！！！
const int mod=1e9+7;
const int N=52;
int n,m;
int a[N][N];
int f[N][N][N][N];

int read()
{
	int x=0,f=1;
	char c=getchar();
	while(c<'0'||c>'9')
	{
		if(c=='-')
		f=-1;
		c=getchar();
	}
	while(c>='0'&&c<='9')
	{
		x=x*10+c-'0';
		c=getchar();
	}
	return x*f;
}

int main()
{
//	freopen("test.in","r",stdin);
    m=read();
    n=read();//快读，不明白的可以查一下，等同于cin>>m>>n;
	for(int i=1;i<=m;i++)
	{
		for(int j=1;j<=n;j++)
		{
			a[i][j]=read();
		}
	} 
	for(int i=1;i<=m;i++)
	{
		for(int j=1;j<=n;j++)
		{
			for(int k=1;k<=m;k++)
			{
				for(int l=1;l<=n;l++)
				{
					f[i][j][k][l]+=a[i][j]+a[k][l];
					f[i][j][k][l]+=max(max(f[i-1][j][k-1][l],f[i-1][j][k][l-1]),max(f[i][j-1][k-1][l],f[i][j-1][k][l-1]));
					if(i==k&&j==l)
					f[i][j][k][l]-=a[i][j];
				}
			}
		}
	}
	cout<<f[m][n][m][n]<<'\n';
	return 0;
}

这两个可以看成板子题吧

1032机器人这个题，我猜是因为两个机器人要同时走，所以与前面两题的区别应该是当走到同一点时要都减掉吧，就是同时退回，，，

好叭确实是这样。

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
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <stack>
#include <vector>
#include <map>
#include <queue>
#include <cstring>
#include <cmath>
#include <set>
#include <iterator>

using namespace std;

typedef long long ll;
#define ios ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define INF 0x3f3f3f3f
//判断是否需要开ll！！！
//判断是否需要初始化！！！
const int mod=1e9+7;
const int N=52;
int n,m;
int a[N][N];
int f[N][N][N][N];

int read()
{
	int x=0,f=1;
	char c=getchar();
	while(c<'0'||c>'9')
	{
		if(c=='-')
		f=-1;
		c=getchar();
	}
	while(c>='0'&&c<='9')
	{
		x=x*10+c-'0';
		c=getchar();
	}
	return x*f;
}

int main()
{
//	freopen("test.in","r",stdin);
    n=read();
    m=read();
    for(int i=1;i<=n;i++)
    {
    	for(int j=1;j<=m;j++)
    	{
    		a[i][j]=read();
		}
	}
	for(int i=1;i<=n;i++)
	{
		for(int j=1;j<=m;j++)
		{
			for(int k=1;k<=n;k++)
			{
				for(int l=1;l<=m;l++)
				{
					f[i][j][k][l]+=a[i][j]+a[k][l];
					f[i][j][k][l]+=max(max(f[i-1][j][k-1][l],f[i-1][j][k][l-1]),max(f[i][j-1][k-1][l],f[i][j-1][k][l-1]));
					if(i==k&&j==l)
					f[i][j][k][l]=f[i][j][k][l]-a[i][j]-a[k][l];
				}
			}
		}
	}
	cout<<f[n][m][n][m]<<'\n';
	return 0;
}

学习最重要的是重复，DP这类问题是这样，其他的也一样，在ACWing上也有类似的题，可以过几天再做一下，当然学校oj上的题也可以再做一遍熟悉一下，放链接吧 2770. 方格取数 啊这个题的数据范围要大得多，，，要注意啦，我做完再回来补题解吧。。。

萌新第一篇博客，若有错误请指教。。。

Orz

If you like this blog or find it useful for you, you are welcome to comment on it. You are also welcome to share this blog, so that more people can participate in it. If the images used in the blog infringe your copyright, please contact the author to delete them. Thank you !

FEATURED TAGS
动态规划
FRIENDS
ESC