题目链接:https://www.nowcoder.com/acm/contest/85/G
思路:
DP 空间可以优化成一维的, 用一维数组的 0 号单元保存左斜对角的值即可。
存图这里真不好理解 = =
AC 代码:
#include <algorithm>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <iostream>
#include <map>
#include <queue>
#include <set>
#include <vector> using namespace std; #define max3(x, y, z) max(max((x), (y)), (z))
#define min3(x, y, z) min(mix((x), (y)), (z))
#define pb push_back
#define ppb pop_back
#define mk make_pair #define debug_l(a) cout << #a << " " << (a) << endl
#define debug_b(a) cout << #a << " " << (a) << " "
#define testin(filename) freopen((filename) ,"r",stdin)
#define testout(filename) freopen((filename) ,"w",stdout) typedef long long ll;
typedef unsigned long long ull; const double PI = 3.14159265358979323846264338327;
const double E = exp();
const double eps = 1e-; const int INF = 0x3f3f3f3f;
const int NINF = 0xc0c0c0c0;
const int maxn = 3e3 + ;
const int MOD = 1e9 + ; int Map[maxn][maxn], Cur[maxn], dp[maxn][maxn];
int main()
{
//testin("data1.in");
int n;
scanf("%d", &n);
memset(Map, NINF, sizeof(Map));
memset(Cur, , sizeof(Cur));
memset(dp, , sizeof(dp));
int vis = + ( * (n - ));
int cur = * n - ;
int i, j; for (int i = ; i < vis - n; i++) {
if (i <= i % n)
Cur[i] = i % n + ;
else {
if (n & )
Cur[i] = (i & ) ? n - : n;
else
Cur[i] = (i & ) ? n : n - ;
}
}
for (int i = vis - ; i >= vis - n; i--)
Cur[i] = vis - i; vector <int> v[vis];
int temp;
for (i = ; i < vis; i++)
{
for (j = ; j < Cur[i]; j++)
{
scanf("%d", &temp);
v[i].push_back(temp);
}
} int len = cur / + ;
int flag = ;
for (i = , j = n; i < len; i++, j++)
{
for (int l = , k = flag; l < j; l++, k++)
{
Map[i][l] = v[k][v[k].size() - ];
v[k].pop_back();
if (v[k].size() == )
flag++;
}
} for (j -= ; i < cur; i++, j--)
{
for (int l = (cur - j), k = flag; l < cur; l++, k++)
{
Map[i][l] = v[k][v[k].size() - ];
v[k].pop_back();
if (v[k].size() == )
flag++;
}
} dp[][] = Map[][];
for (int i = ; i < cur; i++) {
dp[][i] = Map[][i] + dp[][i - ];
dp[i][] = Map[i][] + dp[i - ][];
} for (int i = ; i < cur; i++)
for (int j = ; j < cur; j++)
dp[i][j] = Map[i][j] + max3(dp[i - ][j - ], dp[i - ][j], dp[i][j - ]); cout << dp[cur - ][cur - ] << endl;
return ;
}