题目大意:
有 N×N 的方格图 (N≤9),一部分方格上带有分数,求从(1,1)出发,途径(N,N)再放回(1,1)最多得到多少分数(每个方格只能被获取一次分数)
思路过程:
1.先假设路径只包含从(1,1)出发到达(N,N),不包括返程,则很容易写出对应的二维dp,用dp[i][j]表示到达第i行第j列的最大分数,转移方程式为:
dp[i][j] = max(dp[i - 1][j], dp[i][j - 1])+a[i][j]
2.现在考虑整个路程,因为N<=9,所以可以遍历去程或返程的所有行走路线,再求对应的返程或去程的最大分数
代码如下:
#include<bits/stdc++.h>
#include<algorithm>
typedef long long ll;
using namespace std;
#define N 10
#define M -0x3fffffff
ll a[N][N],load[N][N];int b[20];
ll dp[N][N];
int main(void)
{
ios::sync_with_stdio(0);
int n,y,x; cin >> n;
do{
cin >> x >> y;
cin >> load[x][y];
} while (x && y);
for (int i = n-1; i < 2*(n-1); i++)b[i] = 1;
ll sum = 0;
//遍历所有返程的路线
do {
x = n, y = n;int num = 0;
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= n; j++) {
a[i][j]=load[i][j];
}
}
num += a[n][n]; a[n][n] = 0;
//返程
for (int i = 0; i < (n - 1) * 2; i++) {
//b[i]为1则向下走
if (b[i])x--;
else y--;
num += a[x][y];
a[x][y] = 0;
}
memset(dp, 0, sizeof(dp));
//去程
for (int i = 1; i <= n; i++)
for (int j = 1; j <= n; j++)
dp[i][j] = max(dp[i - 1][j], dp[i][j - 1])+a[i][j];
sum = max(sum, num + dp[n][n]);
} while (next_permutation(b,b+(n-1)*2));
cout << sum;
return 0;
}