• 周二. 9月 27th, 2022

5G编程聚合网

5G时代下一个聚合的编程学习网

热门标签

[51nod1084]矩阵取数问题 V2

admin

11月 28, 2021

题目链接:

51nod1084

题目相当于从上向下走两次,首先可以想到一个Naive的DP:

(f[a][b][c][d])表示一个人当前在((a,b)),另一个在((c,d))时取的最大值。

有一个显然的优化是只用保留(a+b=c+d)的状态(两人同时出发,速度相同)就可以求出答案。

那么有转移方程(f[a][b][c][d]=Max(f[a-1][b][c-1][d],f[a-1][b][c][d-1],f[a][b-1][c-1][d],f[a][b-1][c][d-1])+((a,c)=(b,d)?a[a][b]:a[a][b]+a[c][d]))

但是(n^4)是会爆炸的,我们需要再减少状态数。

发现若知道了(a,b,c),那么就可以求出(d=a+b-c),于是就可以去掉一维。

时间复杂度 (O(n^3))

空间复杂度 (O(n^3))

顺便这题行列输入是反的,莫名多WA一次

代码:

#include <cstdio>

inline int Max(const int a,const int b){return a>b?a:b;}
int m,n,w[205][205],f[205][205][205];

int main()
{
	scanf("%d%d",&n,&m);
	for(int i=1;i<=m;++i)
		for(int j=1;j<=n;++j)
			scanf("%d",&w[i][j]);
	for(int s=2;s<=n+m;++s)//枚举总步数a+b
		for(int a=1;a<=m;++a)
			for(int c=1;c<=m;++c)
			{
				int b=s-a,d=s-c;
				if(b<1||b>n||d<1||d>n)continue;
				int p1=Max(f[a-1][b][c-1],f[a-1][b][c]);
				int p2=Max(f[a][b-1][c],f[a][b-1][c-1]);
				f[a][b][c]=Max(p1,p2)+(a==c?w[a][b]:w[a][b]+w[c][d]);
			}
	printf("%d
",f[m][n][m]);
	return 0;
}

发表回复

您的电子邮箱地址不会被公开。