题解 | #Don't Starve#

链接：https://ac.nowcoder.com/acm/contest/33190/A

分类：dp

A题

先看题

大意：平面上有N个点,你可以从原点出发，前往其他点，然后从到的那一点前往下一点。但是每次走的路程严格小于上一次，求最多能走几次（点可重复经过）。点的坐标为（x,y）（-20000<=x,y<=20000） 共有n(n<2000) 个点。

分析

暴力或DFS都得无

可以选择的是dp，但普通的dp由于需要考虑起止点、方向、距离、次数，时间能到$O(n^4)O(n^4)$,空间到了$O(n^3)O(n^3)$,都不现实，所以要进行优化。

采用倒推，仅从最短的几条边开始计数，毕竟数据不太可能极端得离谱。并且可以只在dp中记录最终的数据

代码+注解

#include<bits/stdc++.h>
using namespace std;
 
template<class T>inline void read(T&x){//快读
    char c,last=' ';
    while(!isdigit(c=getchar()))last=c;
    x=c^48;
    while(isdigit(c=getchar()))x=(x<<3)+(x<<1)+(c^48);
    if(last=='-')x=-x;
}
 
#define ll long long
const int MAXN=2e3+5;
int n,m;
ll x[MAXN],y[MAXN];
int f[MAXN],g[MAXN];
struct node{
    int u,v;
    ll w;
    node(int U,int V,ll W):u(U),v(V),w(W){}
};
vector<node>e;
 
bool cmp(node a,node b){return a.w<b.w;}
 
inline ll d(int u,int v){return (x[u]-x[v])*(x[u]-x[v])+(y[u]-y[v])*(y[u]-y[v]);}
 
int main()
{
    read(n);
    for(int i=1;i<=n;++i)read(x[i]),read(y[i]),e.push_back(node(0,i,d(0,i)));//d(0,i)计算出的即是原点到第 i 个食物点的距离
    for(int i=1;i<n;++i){
        for(int j=i+1;j<=n;++j){
            e.push_back(node(i,j,d(i,j)));
        }
    }
    sort(e.begin(),e.end(),cmp);
    m=e.size();
    for(int l=0,r;l<m;l=r){
        r=l;
        while(r<m&&e[l].w==e[r].w)++r;//将边权相同的边平行处理
        for(int j=l;j<r;++j)g[e[j].u]=f[e[j].u],g[e[j].v]=f[e[j].v];//将可能更新的店的缓存数组初始化
        for(int j=l,u,v;j<r;++j){
            u=e[j].u,v=e[j].v;
            g[u]=max(g[u],f[v]+1);
            if(!u)continue;//如果是 0 到某个食物点的边,视作单向边不反向处理
            swap(u,v);//反向处理
            g[u]=max(g[u],f[v]+1);
        }
        for(int j=l;j<r;++j)f[e[j].u]=g[e[j].u],f[e[j].v]=g[e[j].v];//更新
    }
    cout<<f[0]<<'\n';
    return 0;
}

点个赞呗