DP数组：
第一维度维护的是在传的过程中纵坐标与横坐标的和。
在同一斜线上，剩下表示两个点的从坐标就可以表示这两个点的位置。
第二维度维护的是相对在左边的点的纵坐标。
第三维度维护的是相对在右边的点的纵坐标。
当查询一个情况时，只有四种情况可以到他
1
|
F[sum][i][j]=max{F[sum-1][i][j]+F[sum-1][i][j-1]+F[sum-1][i-1][j]+F[sum-1][i-1][j-1]}
|
sum-1 i j 即为i,j在横坐标上左移1
sum-1 i-1 j 即为i在纵坐标上上移1
sum-1 i j-1 同理
sum-1 i-1 j-1 i,j在纵坐标上上移1
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
|
#include<iostream>
#include<cstring>
#define SUM 1001
#define COL 101
using namespace std;
int m, n;
int dp[SUM][COL][COL], a[1001][1001];
int main()
{
cin >> m >> n;
for(int i = 1; i <= m; i++)
{
for(int j = 1; j <= n; j++)
{
cin >> a[i][j];
}
}
memset(dp, -1, sizeof(dp));
dp[2][1][1] = 0;
for(int k = 3; k < m + n; k++)
{
for(int i = 1; i < n; i++)
{
for(int j = i + 1; j <= n; j++)
{
dp[k][i][j] = max(dp[k][i][j],max(dp[k - 1][i][j], max(dp[k - 1][i - 1][j], max(dp[k - 1][i][j - 1], dp[k - 1][i - 1][j - 1])))) + a[k - i][i] + a[k - j][j];
}
}
}
cout << dp[m + n - 1][n - 1][n] << endl;
return 0;
}
|