蓝桥杯算法训练VIP-方格取数

题目

题目链接

题解

动态规划。

本题和这个题几乎是完全一样，那个博客写的巨清楚，所以这里不写了。

代码

#include<bits/stdc++.h>
using namespace std;
const int N = 20;

int dp[N][N][N][N], n, x, y, v, a[N][N];

int max(int a, int b, int c, int d) {
	return max(max(a, b), max(c, d));
}

int main()
{
	cin>>n;
	while(cin>>x>>y>>v && x && y && v) a[x][y] = v;
	
	for(int i = 1;i <= n;i ++)
	for(int j = 1;j <= n;j ++)
	for(int p = 1;p <= n;p ++) {
		int q = i+j-p;
		if(q < 1 || q > n) continue;
		dp[i][j][p][q] = max(dp[i-1][j][p-1][q],
							 dp[i-1][j][p][q-1],
							 dp[i][j-1][p-1][q],
							 dp[i][j-1][p][q-1]
							);
		dp[i][j][p][q] += a[i][j] + (i==p&&j==q?0:a[p][q]); // 两个人都走过这个位置就只加一次 
	} 	
	cout << dp[n][n][n][n];
	return 0;
}