2022牛客多校（五）

2022牛客多校（五）

一、比赛小结

比赛链接："蔚来杯"2022牛客暑期多校训练营5

这场是草酸哥出的一套题，最后 unrated 了

二、题目分析及解法（基础题） A、Don’t Starve

题目链接：A-Don’t Starve

题意：

给定 n 个点有食物（每个点可以吃多次），每个点有一个坐标，对与行走的规则是每一步都必须严格短于上一步，问最优的方案下能够吃到多少次食物

题解：

观察可得，当你站在某一个特定的点上时，会影响你的接下来转移的只有上一步所走的距离具体是多少，但如果想把上一步的距离设入状态的话内存是不允许的。所以我们考虑设立状态dp[i][j]表示上一步在i，当前这步走到j了的情况下最多已经吃到次数是多少，而对于转移，因为我们知道了最近两步的行走

所以可以直接计算出上一步的长度从而进行转移了，复杂度O(n^2)

代码：

#include 
using namespace std;
const int maxn = 2e3 + 5;
const int Max = 0x3f3f3f3f;
int n;
int x[maxn], y[maxn];
struct Edge {
  int u, v, dis;
  Edge(int u = 0, int v = 0, int dis = 0) : u(u), v(v), dis(dis) {}
  bool operator a.dis; }
};
vector e;
int f[maxn], g[maxn];
int main() {
  ios::sync_with_stdio(0);
  cin.tie(0), cout.tie(0);
  memset(f, -Max, sizeof f);
  cin >> n;
  for (int i = 1; i > x[i] >> y[i];
  for (int i = 0; i