在一个笛卡尔平面上，有n个点。 从原点出发，只能在n个点之中以严格递减的欧几里得距离移动， 求经过的点的最多个数。
1 ≤ N ≤ 2000 1≤N≤2000 1≤N≤2000 − 10000 ≤ X i ， Y i ≤ 10 , 000 −10000≤X_i，Y_i≤10,000 −10000≤Xi，Yi≤10,000
由于一开始没有思路，就打了暴力搜索，这里不展示。 6分
然后发现搜索中有很多分支重复搜索了，就加了记忆化，记录从上一个点来当前点的已经经过的点数。 54分 代码如下：
#include<bits/stdc++.h> using namespace std; int n,sum,ff[2006][2006]; struct A{ int x,y; }_[2003]; struct B{ int to; double s; }t; bool cmp(B a,B b){ return a.s<b.s; } vector <B> f[2003]; int dfs(int l,int _,double an){ if(ff[l][_]!=-1)return ff[l][_]; int i=0,cnt=0; while(i<n-1){ int x=f[_][i].to; double y=f[_][i].s; if(f[_][i].to!=_){ if(f[_][i].s>=an)break; cnt=max(cnt,dfs(_,f[_][i].to,f[_][i].s)); } i++; } return ff[l][_]=cnt+1; } int main(){ memset(ff,-1,sizeof(ff)); scanf("%d",&n); for(int i=1;i<=n;i++){ scanf("%d%d",&_[i].x,&_[i].y); } for(int i=1;i<n;i++){ for(int j=i+1;j<=n;j++){ t.s=sqrt((_[i].x-_[j].x)*(_[i].x-_[j].x)+(_[i].y-_[j].y)*(_[i].y-_[j].y)); t.to=i; f[j].push_back(t); t.to=j; f[i].push_back(t); } } for(int i=1;i<=n;i++) sort(f[i].begin(),f[i].end(),cmp); for(int i=1;i<=n;i++){ sum=max(sum,dfs(0,i,sqrt(_[i].x*_[i].x+_[i].y*_[i].y))); } printf("%d",sum); return 0; }以下正解
我们可以在两两点之间建边，设两点之间的距离为边的边权。 所以我们需要求的就是 完全图中边权严格下降的路径经过的最多节点数（可重复经过一个点）。
由于边权是严格下降的，所以边权一定要进行排序，当然边连接的点也要在参与排序的结构体中。
设这个结构体数组为 A[i] 。
进行升序排序后，我们可以发现 最短边连接的点在此时只能到达这条边连接的另一个点。
我们可以设一个 best[i] 数组记录 i 点在一条路径上可到达的最多点数。（那么答案就是 best[0] ） 设边权为 s ( A[i].s ) ，边连接的两个点分别为 a ( A[i].a ) 和 b ( A[i].b ) 。
那下一条边（倒数第二短）呢…
通过枚举画图可知 b e s t [ a ] = m a x ( b e s t [ a ] , b e s t [ b ] + 1 ) best[a]=max(best[a],best[b]+1) best[a]=max(best[a],best[b]+1) b e s t [ b ] = m a x ( b e s t [ b ] , b e s t [ a ] + 1 ) best[b]=max(best[b],best[a]+1) best[b]=max(best[b],best[a]+1)
但是，当两条边权相等的边相接时，这里出现了错误， 因为升序数组中相等的数也是排在一起的，这不符合题目严格下降的要求。
怎么判断这种情况？
我们要再开一个 lste[i] 数组记录 i 点连上的最长边的边权， 如果 lste[i]==s ,说明 i 点连上了两条边权相等的边。
如何解决这个问题？
加一个数组 nbest[i] 表示 枚举的边为当前的边权时 i 点在一条路径上可到达的最多点数, 替换原来的 best 数组， best[i] 数组遇到新的边权的边时再进行更新，值为 nbest[i] 。
原点处还有点细节，这里不再赘述。
代码如下：
#include<bits/stdc++.h> using namespace std; int n,x[2003],y[2003],k=1,s,a,b; int best[2003],nbest[2003],lste[2003]; struct W{ int s,a,b; }A[4000006]; bool cmp(W a,W b){return a.s<b.s;} int main(){ scanf("%d",&n); for(int i=1;i<=n;i++){ scanf("%d%d",&x[i],&y[i]); } for(int i=0;i<n;i++){ for(int j=i+1;j<=n;j++){ A[k].a=i;A[k].b=j; A[k++].s=(x[i]-x[j])*(x[i]-x[j])+(y[i]-y[j])*(y[i]-y[j]); } } sort(A,A+n*(n+1)/2,cmp); for(int i=0;i<n*(n+1)/2;i++){ s=A[i].s; a=A[i].a; b=A[i].b; if(s!=lste[a]){ best[a]=nbest[a]; lste[a]=s; } if(s!=lste[b]){ best[b]=nbest[b]; lste[b]=s; } if(a==0){ nbest[a]=max(nbest[a],best[b]+1); } else{ nbest[a]=max(nbest[a],best[b]+1); nbest[b]=max(nbest[b],best[a]+1); } } printf("%d",nbest[0]); }