A题: Don’t Starve

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

题目大意

在二维平面上，有 $n(1\le n\le 2000)$ 个位置有食物。从原点出发，每次直线前往其他任意一个有食物的位置收集食物。收集完后再次前往下一个点。每当离开一个有食物的点后，该点的食物就会刷新。并且每次的移动距离必须严格递减。

题解

称食物点间的距离为边权。
为了方便处理 初始从原点开始 这个条件，我们可以考虑反向进行 $dp$ 。
设状态 $d{p}_x$ 表示从点 $x$ 出发后能达到的最多食物点数，因为是反向 $dp$ ，我们按边权从小到大枚举边进行转移，这样可以保证每次向前转移时，后面的边权一定是比当前边小的。
转移式显然:
$$d{p}_x=d{p}_y+1$$

注意点

对于相同边权的边，平行进行处理(可以将更新后的值存入一个缓存数组，待相同边权全部转移后再更新)，防止出现转移时前后边权相同(非严格递减)的情况。
存边权时直接使用 $(x_i-x_j{)}^2+(y_i-y_j{)}^2$ 代替即可，不需要开方，防止出现精度误差。

参考代码

#include
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;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54