题解 | #Don't Starve#

说说$AA$题吧，毕竟考试结束才写对，设$f[i][j]f[i][j]$表示从i走到j后还能走拿多少食物，这样设状态是因为这个状态与之前的状态无关，得到转移方程$f[i][j]=max(f[j][k])f[i][j]\; =\; max(f[j][k])$其中，$j->kj->k$这条路的长度小于$i->ji->j$的长度，因此想到先将所有边按长度从小到大排序，这样在考虑当前的路时，之前的路都是可以走的，可以用$s[i]s[i]$表示目前从i出发最远可以走多远，注意如果有长度相同通往同一个点的路，应该同时被考虑到，一直过不了是因为不小心计算了$f[i][0]f[i][0]$，使用其去更新$s[i]s[i]$的答案，因为0是起始点，因此不应该考虑进来

#include <iostream>
#include <algorithm>
using namespace std;
const int maxn = 5000006;
const int maxm = 2003;
struct edge {
    int u, v, w;
}ed[maxn];
int n, cnt;
int x[maxn], y[maxn];
longlong s[maxm];
long long f[maxm][maxm];
bool cmp (edge x, edge y)
{
    return x.w < y.w;
}
int main ()
{
    bool flag = false;
    cin >> n;
    for (int i = 1; i <= n; ++i) {
        cin >> x[i] >> y[i];
        if (!x[i] && !y[i]) flag = true;
        for (int j = 0; j < i; ++j) ed[++cnt] = edge{i, j, (x[i] - x[j]) * (x[i] - x[j]) + (y[i] - y[j]) * (y[i] - y[j])};
    }
    sort(ed + 1, ed + cnt + 1, cmp);
    for (int i = 1; i <= cnt; ++i) {
        int j = i;
        while (ed[i].w == ed[j + 1].w && j < cnt) ++j;
        for (int k = i; k <= j; ++k) {
            int u = ed[k].u, v = ed[k].v;
            if (v)  f[u][v] += s[v] + 1;
            if (u)  f[v][u] += s[u] + 1;
        }
        for (int k = i; k <= j; ++k) {
            int u = ed[k].u, v = ed[k].v;
            if (u)  s[u] = max(s[u], f[u][v]);
            if (v)  s[v] = max(s[v], f[v][u]);
        }
        i = j;
    }
    long long ans = 0;
    for (int i = 1; i <= n; ++i) ans = max(ans, f[0][i]);
    cout << ans + flag << endl;
    return 0;
}