题目链接
https://www.nowcoder.com/acm/contest/85/G
思路
按照题解上的方式 存取数据 然后DP一下 就可以了
AC代码
#include <cstdio> #include <cstring> #include <ctype.h> #include <cstdlib> #include <cmath> #include <climits> #include <ctime> #include <iostream> #include <algorithm> #include <deque> #include <vector> #include <queue> #include <string> #include <map> #include <stack> #include <set> #include <numeric> #include <sstream> #include <iomanip> #include <limits> using namespace std; typedef long long ll; typedef unsigned long long ull; typedef pair <int, int> pii; typedef pair <ll, ll> pll; const double PI = 3.14159265358979323846264338327; const double E = exp(1); const double eps = 1e-6; const int INF = 0x3f3f3f3f; const int maxn = 3e3 + 5; const int MOD = 1e9 + 7; int Map[maxn][maxn], Cur[maxn], dp[maxn][maxn]; int main() { int n; scanf("%d", &n); memset(Map, 0xc0, sizeof(Map)); memset(Cur, 0, sizeof(Cur)); memset(dp, 0, sizeof(dp)); int vis = 1 + (4 * (n - 1)); int cur = 2 * n - 1; int i, j; for (i = 0; i < n; i++) Cur[i] = i + 1; int opt[2]; opt[i % 2] = n - 1; opt[!(i % 2)] = n; int flag = i % 2;; for ( ; i < (vis - n); i++, flag = !flag) Cur[i] = opt[flag]; for (j = n ; i < vis; i++, j--) Cur[i] = j; vector <int> v[vis]; int temp; for (i = 0; i < vis; i++) { for (j = 0; j < Cur[i]; j++) { scanf("%d", &temp); v[i].push_back(temp); } } int len = cur/2 + 1; flag = 0; for (i = 0, j = n; i < len; i++, j++) { for (int l = 0, k = flag; l < j; l++, k++) { Map[i][l] = v[k][v[k].size() - 1]; v[k].pop_back(); if (v[k].size() == 0) flag++; } } for (j -= 2; i < cur; i++, j--) { for (int l = (cur - j), k = flag; l < cur; l++, k++) { Map[i][l] = v[k][v[k].size() - 1]; v[k].pop_back(); if (v[k].size() == 0) flag++; } } dp[0][0] = Map[0][0]; for (i = 1; i < cur; i++) { dp[0][i] = dp[0][i - 1] + Map[0][i]; dp[i][0] = dp[i - 1][0] + Map[i][0]; } for (i = 1; i < cur; i++) { for (j = 1; j < cur; j++) dp[i][j] = max(max(dp[i - 1][j], dp[i][j - 1]), dp[i - 1][j - 1]) + Map[i][j]; } cout << dp[cur - 1][cur - 1] << endl; }转载于:https://www.cnblogs.com/Dup4/p/9433236.html
