P1004 [NOIP2000 提高组] 方格取数

链接

https://www.luogu.com.cn/problem/P1004

题目

思路

dp[i][j]=max(dp[i-1][j],dp[i][j-1])+mp[i][j]

当走两遍：转换为四维dp:dp[i][j][k][l]。当(i= =j&&k==l)时,减去mp[i][j]。

代码

#define _CRT_SECURE_NO_WARNINGS
#include<iostream>
#include<algorithm>
#include<queue>
#include<cmath>
#include<map>
#include<string.h>
#include<string>
#include<vector>
#define IOS ios::sync_with_stdio(false),cin.tie(0),cout.tie(0)
using namespace std;
#define int long long
const int N = 15;

int mp[N][N];
int dp[N][N][N][N];

signed main()
{
	IOS;
	int n; cin >> n;
	while (true)
	{
		int a, b, c; cin >> a >> b >> c;
		if (a == 0 and b == 0 and c == 0)break;
		mp[a][b] = c;
	}
	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(max(dp[i - 1][j][k - 1][l], dp[i - 1][j][k][l - 1]),
						max(dp[i][j - 1][k - 1][l], dp[i][j - 1][k][l - 1])) + (mp[i][j] + mp[k][l]);
					if (i == k and j == l)dp[i][j][k][l] -= mp[i][j];
				}
	cout << dp[n][n][n][n];

	return 0;
}