牛客小白月赛1 G あなたの蛙は旅⽴っています【DP】

题目链接

https://www.nowcoder.com/acm/contest/85/G

思路

牛客小白月赛1   G	あなたの蛙は旅⽴っています【DP】

按照题解上的方式 存取数据

然后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;
}
上一篇:必须正确理解的---ng指令中的compile与link函数解析


下一篇:记一次使用修改字节码的方法解决java.lang.NoSuchMethodError