四维dp例题

四维dp便是维护4个状态的dp方式

拿题来说吧。

1. 洛谷P1004 方格取数

#include<iostream>

#include<cstdio>

using namespace std;

const int maxn=12;

int n;

int map[maxn][maxn];

int dp[maxn][maxn][maxn][maxn];

int main(){

	cin>>n;

	int x,y,z;

	while(cin>>x>>y>>z&&(x!=0||x!=0||z!=0)){

		map[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++){

					dp[i][j][k][l]=max(dp[i-1][j][k-1][l],max(dp[i-1][j][k][l-1],max(dp[i][j-1][k-1][l],dp[i][j-1][k][l-1])))+map[i][j]+map[k][l];

					if(i==k&&j==l)

						dp[i][j][k][l]-=map[k][l];

				}

	}

	cout<<dp[n][n][n][n];

	return 0;

}

本题便是一个四维dp例题

分析题目

发现维护两个dp数组或者进行两次dp不是很现实

观察到数据范围较小

便可以考虑四维dp

我们将走两次抽象成两个人同时走

我们以dp[i] [j] [k] [l]表示第一个人走到i j

第二个人走到 k l 时的总体最大值

我们便对i j k l 进行枚举

因为两人所走道路不能重合

所以当 i=k j=l时减去多加的那个就可以

2. 洛谷P1006 传纸条

#include<iostream>

using namespace std;

const int maxn=90;

int n,m;

int map[maxn][maxn];

int dp[maxn][maxn][maxn][maxn];

int main(){

	cin>>m>>n;

	for(int i=1;i<=m;i++){

		for(int j=1;j<=n;j++){

			cin>>map[i][j];

		}

	}

	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++){

					dp[i][j][k][l]=max(dp[i-1][j][k-1][l],max(dp[i-1][j][k][l-1],max(dp[i][j-1][k-1][l],dp[i][j-1][k][l-1])))+map[i][j]+map[k][l];

					if(i==k&&j==l)

						dp[i][j][k][l]-=map[k][l];

				}

	}

	cout<<dp[m][n][m][n];

	return 0;

}

基本就是同一题

双倍经验

还有滚动数组优化，

以后再更新

巴特西

四维dp,传纸条，方格取数

四维dp例题

1. 洛谷P1004 方格取数

2. 洛谷P1006 传纸条

最新文章

热门文章