[2022 Nioke Duo School 5 A Question Don't Starve] DP

题目描述

NIO purchased a new game, Don’t Starve, a sandbox game published by Klei Entertainment Inc. This game revolves around a scientist named Wilson who finds himself in a dark and gloomy world and must survive for as long as possible.

In the very beginning, NIO should help Wilson to gather some food for survival. Assume that when controlling Wilson to walk towards a location on the map, NIO should keep pressing the left button on the mouse, and when Wilson comes to the place where there is food, NIO should stop pressing the mouse, but press the space key on the keyboard to collect the food at this location. As NIO will feel tired of pressing the mouse for a long time and his finger will become very uncomfortable after a long time of pressing, the time he is willing to press the mouse after each collection is strictly decreased. Suppose there are NN locations on the 2-D plane, and at each point, there is only one unit of food. And NIO will start at the original point on the plane. You can assume that each point has an infinite number of food items, but only one can be taken at a time.

What is the maximum amount of food can NIO get for Wilson? Note that the food will be refreshed after Wilson left.

输入输出描述

样例输入

7
-7 21
70 64
45 -52
68 -93
-84 -16
-83 64
76 99

样例输出

4

题意：

给你n个点,Each point has a food,Each point also has a coordinate,You can walk between these points,The distance each time must be strictly less than the length of the previous time,Ask how much food you can eat.

思路：

因为数据量是2000,So the distance between every two points can be 4e6的时间处理出来,然后这就是2000个点,4e6条边,complete timeok,Then set the statusdp[i]表示从(0,0)点到第iThe maximum amount of food one can eat,Then first sort all the sides by length from largest to smallest,然后从前往后dpThat distance can be guaranteed to decrease,There are also some distances that are equal,需要在dpWhen processing out all edges with the same distance,Then save the value inside to avoid itdpWhen the original value is replaced, it will be updated later,Repeated,equivalent to a ring,Then take a look at the code

#include<bits/stdc++.h>
using namespace std;
const int N = 2010;
#define int long long 
#define x first
#define y second
struct node{
    
	int x,y,w,id;
	bool operator<(const node&t)const{
    
		return w > t.w;
	}
}e[N*N];
typedef pair<int,int> PII;
int dis(PII a,PII b){
    
	return (a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y);
}
PII loc[N];
int f[N*N];
signed main(){
    
	int n,tt=0;
	while(scanf("%lld",&n)!=EOF){
    
		tt = 0;
		for(int i=1;i<=n;i++){
    
			scanf("%lld%lld",&loc[i].x,&loc[i].y);
			e[++tt] = {
    i,1,dis(loc[0],loc[i]),1};
			f[i] = -1e9;
		}
		for(int i=1;i<=n;i++)
			for(int j=1;j<=n;j++)
				if(i != j) e[++tt] = {
    i,j,dis(loc[i],loc[j]),0};
		sort(e+1,e+1+tt);
		for(int i=1;i<=tt;){
    
			int j = i;
			queue<PII> q;
			while(j<=tt&&e[i].w == e[j].w) j++;
			for(int k=i;k<j;k++) if(e[k].id) q.push({
    e[k].x,1});
			else q.push({
    e[k].x,f[e[k].y]+1});
			while(q.size()) f[q.front().x] = max(f[q.front().x],q.front().y),q.pop();
			i=j;
		}
		int ans = 0;
		for(int i=1;i<=n;i++) ans = max(ans,f[i]);
		cout<<ans<<endl;
	}
	return 0;
}