"蔚来杯"2022牛客暑期多校训练营5-A Don’t Starve

题目描述

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

解析

每次去到的下一个点的距离都要递减，但是如果每次都选择最长的，可能不是最优解。如图为一个反例 1->2->3很明显收集到的食物不如

1->5->3

而因为离开一个点后可以返回，所以可以反向$dpdp$，只要保证最后的一个点为0即可，输出答案为$d{p}_{0}dp\_0$

定义dp[i]为从i点出发所取得的最大食品数。 所以状态转移方程为:

$d{p}_i=1+max(d{p}_j)dp\_i=1+max(dp\_j)$

$dpdp$前先从大到小排序，保证边的长度由大到小。

上代码

#include<bits/stdc++.h>
using namespace std;
#define ll long long
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;
}
const int MAXN=2e3+5;
int n,m;
ll x[MAXN],y[MAXN];
int dp[MAXN],g[MAXN];
struct node{
	ll u,v,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)));//两点之间的距离
	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]=dp[e[j].u],g[e[j].v]=dp[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],dp[v]+1);
			if(!u)continue;//如果是0出发的点就不做反向处理
			swap(u,v);//相反处理
			g[u]=max(g[u],dp[v]+1);
		}
		for(int j=l;j<r;++j)dp[e[j].u]=g[e[j].u],dp[e[j].v]=g[e[j].v];
	}
	cout<<dp[0]<<"\n";
	return 0;
}