题解 | #Don't Starve#

题目描述

在二维平面上，有n（1<=n<=2000）个位置有食物。从原点出发，每次直线前往其他任意一个有食物的位置收集食物。收集完后再次前往下一个点。每当离开一个食物的点后，该点的食物就会刷新。并且每次的移动距离必须严格下降。
求最多可以收集到多少食物。

胡乱分析

我们将题目看作是一些海岛分布在海上，食物分布在每一个岛上，你从一个岛出发去另一个岛to get the food that you need。你可以回到原来的岛，但是去每一个岛的距离需要递减。至此，一部分people可能想到每次选择最远的岛，但是这明显是错的，具体见下图
这个是海岛的分布

这个是当你连接最远的时候只能连接一部分

这个是完全连接的时候。
所以当我们拍烂脑子想很久都想不出来时，我们可以联想到反向DP，类似于其他的题的做法

https://www.luogu.com.cn/problem/P6648

所以
我们设$d{p}_{x}dp\_x$表示从点x出发后能到达的最多食物点 ，然后我们按岛与岛之间的距离从小到大作为转移关系，从而能一直前往下一个海岛，所以方程式为：
$d{p}_{x}dp\_x$=$d{p}_{y}dp\_y$+1

注意

这里距离$(a\mathrm{.}x-b\mathrm{.}x{)}^2(a.x-b.x)^2$-$(a\mathrm{.}y-b\mathrm{.}y{)}^2(a.y-b.y)^2$不需要开方，可能会使答案变形，直接用平方存着。

代码出锅

#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 cxk{
	int u,v;
	ll w;
	cxk(int U,int V,ll W):u(U),v(V),w(W){}
};
vector<cxk>e;

bool cmp(cxk a,cxk 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]);//2点间距离公式 
}
int main()
{
	read(n);
	for(int i=1;i<=n;++i)
	{
		read(x[i]);
		read(y[i]);
		e.push_back(cxk(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(cxk(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";
}