为什么搬方格取数的代码可以过?
查看原帖
为什么搬方格取数的代码可以过?
242490
lyc呐楼主2020/9/21 11:22

这里是i==k && j==l就去重减去一次,但是为什么可以防止两条路径相交呢?

#include<iostream>
#include<cstring>
#include<vector>
using namespace std;

const int N = 55;
int g[N][N];
int f[N][N][N][N];
int n, m;

int main()
{
	cin.tie(0);
	ios::sync_with_stdio(false);
	
	cin >> n >> m;
	int a, b, c;
	
	for(int i = 1 ; i <= n ; i ++)
		for(int j = 1 ; j <= m ; j ++)
			cin >> g[i][j];
	
	
	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] = 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]) )	+ g[i][j] + g[k][l];
					if(i == k && j == l)
						f[i][j][k][l] -= g[i][j];
				}
	
	cout << f[n][m][n][m];
}
2020/9/21 11:22
加载中...