說說$AA$題吧，畢竟考試結(jié)束才寫對，設(shè)$f[i][j]f[i][j]$表示從i走到j(luò)后還能走拿多少食物，這樣設(shè)狀態(tài)是因?yàn)檫@個(gè)狀態(tài)與之前的狀態(tài)無關(guān)，得到轉(zhuǎn)移方程$f[i][j]=max(f[j][k])f[i][j]\; =\; max(f[j][k])$其中，$j?>kj->k$這條路的長度小于$i?>ji->j$的長度，因此想到先將所有邊按長度從小到大排序，這樣在考慮當(dāng)前的路時(shí)，之前的路都是可以走的，可以用$s[i]s[i]$表示目前從i出發(fā)最遠(yuǎn)可以走多遠(yuǎn)，注意如果有長度相同通往同一個(gè)點(diǎn)的路，應(yīng)該同時(shí)被考慮到，一直過不了是因?yàn)椴恍⌒挠?jì)算了$f[i][0]f[i][0]$，使用其去更新$s[i]s[i]$的答案，因?yàn)?是起始點(diǎn)，因此不應(yīng)該考慮進(jìn)來

#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;
}