题解 | #Don't Starve#

若出现证明错误请指明，个人思路。

图中$nn$个点构成共$n\times (n-1)n\times (n\; -\; 1)$条无向边的完全图，从原点开始沿着一个严格递减的路径最远可以走到多少点。

很明显的想法就是从原点开始dfs所有可行路径，但是会出现环路走到之前经过的点导致复杂度过高，但可以发现搜索进行过程中一个事实：考虑任意一个环上的起点，从该点选择一条距离$di{s}_{1}dis\_1$的出边后经过一系列移动再到该点时只会选择严格小于$di{s}_{1}dis\_1$的出边。

所以可以把每个点的$n-1n-1$条出边按权值排序，每次向下搜索时先递归搜索小的边并同时维护$ff$数组（$f[i][j]f[i][j]$代表在$ii$结点位置选择他的前$jj$条出边中最多可以经过多少点）和$visvis$数组（$vis[i]vis[i]$代表$ii$结点位置已经递归完成了第$00$到第$vis[i]vis[i]$条出边并记录在$ff$数组中），这样保证出现环路时可以直接取这个值即可无需继续递归下去。

每次递归时考虑当前点可能已经完成了一些出边的递归，即已经维护出了$f[i][0]\mathrm{.}\mathrm{.}\mathrm{.}f[i][vis[i]]f[i][0]\; ...\; f[i][vis[i]]$，假设当前可以走的边为$\mathrm{0...}index0...index$（即）， 若$vis[i]>=indexvis[i]\; >=\; index$ 直接把$f[i][index]f[i][index]$作为递归结果即可，若则需递归处理第$vis[i]+1vis[i]\; +\; 1$到第$indexindex$条出边并维护$ff$数组和$visvis$数组。

我比赛时写的$indexindex$的查找过程是通过二分查找优化时间复杂度，因为每个点的边都是通过权值排好序的。

每条边最多只会被枚举到常数次，即递归级别$n^{2}n^2$，每次二分查找$indexindex$为$O(lo{g}_n)O(log\_n)$，所以时间复杂度是$O(n^{2}lo{g}_n)O(n^2log\_n)$。

AC代码

//木の処舞う所に，火は燃ゆる。
#include <iostream>
#include <cstdio>
#include <iomanip>
#include <algorithm>
#define int long long
#define endl '\n'
#define inf 0x3f3f3f3f
#define debug printf("Hello World\n")
#define ios ios::sync_with_stdio(false)
using namespace __gnu_cxx;
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int, int> PII;
const int mod1 = 1e9 + 7, mod2 = 998244353;
const long double PI = 3.1415926535898, Ee = 2.718281828459;
const int dx[] = {0, 1, 0, -1}, dy[] = {1, 0, -1, 0};
int gcd(int x,int y) {return y ? gcd(y, x % y) : x;}
const int N = 2000+ 10, M = 3e4 + 10;

int x[N], y[N];
struct edge{
    int v, dis;
    bool operator < (const edge& y) const{
        return dis < y.dis;
    }
};
vector<edge> e[N];
int f[N][N], vis[N], n;

int dfs(int u, int last_dis)
{
    if(e[u][0].dis >= last_dis) return 1;

    int l = 0, r = n - 2;
    while(l < r)
    {
        int mid = l + r + 1 >> 1;
        if(e[u][mid].dis < last_dis) l = mid;
        else r = mid - 1;
    }

    int index = l;
    if(index <= vis[u]) return f[u][index] + 1;

    for(int i = vis[u] + 1;i <= index;i ++)
    {
        int v = e[u][i].v, dis = e[u][i].dis;
        if(i > 0) f[u][i] = max(f[u][i - 1], dfs(v, dis));
        else f[u][i] = dfs(v, dis);
    }

    vis[u] = index;
    return f[u][index] + 1;
}

void solve()
{
    cin>>n;
    for(int i = 1;i <= n;i ++) cin>>x[i]>>y[i];
    for(int i = 1;i <= n;i ++)
    {
        for(int j = 1;j <= n;j ++) if(i != j)
                e[i].push_back({j, (x[i] - x[j]) * (x[i] - x[j]) + (y[i] - y[j]) * (y[i] - y[j])});
        sort(e[i].begin(), e[i].end());
    }
    memset(vis, -1, sizeof vis);
    int res = 0;
    for(int i = 1;i <= n;i ++)
        res = max(res, dfs(i, x[i] * x[i] + y[i] * y[i]));
    cout<<res<<endl;
}

signed main()
{
    ios;
    int t = 1; //t = read();
    while(t --) solve();
    return 0;
}