[NOI2010] 成长快乐题解

初步分析

nemo 肯定走直线。

不妨把 nemo 想象成只能以速度 $v$ 运动或静止。而在最优策略中，nemo 显然不会静止不动。

所以 nemo 的最优策略一定取如下形态：以某种顺序把食物排成一列 $\{p_i\}$ ，从 $\{p_1\}$ 开始一个一个吃，每次都走当前最短时间对应路径。

因为 nemo 已知了各食物的位置和速度，nemo 可以在目标食物的路径上某点等待，而最优的该点必然满足 nemo 和食物同时到达。因而可以计算出其到单个食物所需的最短时间。

简单的高中解三角形问题，这里不再赘述。设 nemo 与食物距离为 $s$ ，食物运动的方向与 nemo 相对于食物的方向夹角为 $\theta$ ，nemo 速度为 $v$ ，食物速度为 $u$ ，联合运用向量点积和余弦定理得出 nemo 走到食物的最短时间为

t=s\frac{u\cos\theta\pm\sqrt{u^2(\cos^2\theta-1)+v^2}}{u^2-v^2}

等式成立性与加减号取法：

当 $\Delta=u^2(\cos^2\theta-1)+v^2<0$ 或 $\cos\theta<0\&\& u>v$ 时，nemo 追不上。
否则取减号一定更优并且 $t$ 必为正。证明就是用 $\Delta\ge 0$ 化一下。
特别地， $u=v$ 特判掉。

目标变为求最优的排列 $\{p_i\}$ 。

点一

就两个点手玩都可以啊喂

点二

枚举全部 $8!=40320$ 种排列。

点三

特点：nemo 一开始体重太小而食物权值呈 $2$ 的整次幂。

只能从小往大吃。

点四

特点：所有食物与 nemo 共线且静止不动。所有食物权值不过 200。

先慢慢增大自己的体重，达到一定量可以吃所有食物后进行区间 DP 即可。

点五，六

特点：所有食物在高空以高速下落，水平位置相隔近。nemo 速度小，但可以吃所有食物。

可以看做 nemo 只能在横轴上运动，接住下落的食物。

设 $f_i$ 表示接住第 $i$ 个食物所能获得的最大体重，直接转移。

点六有一个坑在于有两个食物会同时下落到相同位置。

点七，八

特点：如图。数字三角形的形态已经很明显了。观察权值发现每一行只能选一个，而时间恰好够 nemo 走到最后一排。

数字三角形即可。

点九

特点：所有食物静止

跟点十一起做。

点十

特点：好像没有

这道题唯一折磨人的点。

考虑一个贪心策略：每次在当前所有能吃的食物中按某种关系选出最优的那一个并吃掉。重复该流程直至找不到可以吃的食物为止。

设对于一个食物 $i$ ，其权值为 $w_i$ ，nemo 吃掉它所需时间为 $t_i$ ，nemo 吃掉它时 nemo 的位置距当前位置为 $d_i$ 。

肯定会有一些感性的认识： $w_i$ 越大越好， $t_i$ 越小越好， $d_i$ 越小越好， $\frac{w_i}{t_i}$ 越大越好 $\cdots$

各人有各人的偏好，各种调参方法都能过，但调参的过程无一例外的折磨。这里题解采用

k_i=\frac{w_i}{t_i^2}+\frac{1}{K_1d_i}+K_2

每次选 $k_i$ 最大的吃。 $K_1,K_2$ 为两个 $[1,10]$ 的随机数。

多次贪心取最优解。实测在 10 次之内可以出答案，所花时间不超过 5s。

double eat2(){
	while(!pq.empty())pq.pop();
	double ct,nans=w0,nt=0;nx=fx,ny=fy,pa=0;
	for(int i=1;i<=n;i++){
		fl[i]=0;
		if(w[i]<nans){
			ct=calnt(i,nt);
			pq.push(make_pair(w[i]/(ct*ct)+G/dis(nx,ny,ax[i]+nt*mx[i],ay[i]+nt*my[i])+rand()%10,i));
		}
	}
	while(!pq.empty()){
		int ng=pq.top().second;pq.pop();
		fl[ng]=1,ct=calnt(ng,nt);
		if(nt+ct>T)break;
		nx=ax[ng]+(nt+ct)*mx[ng];
		ny=ay[ng]+(nt+ct)*my[ng];
		na[++pa]=(eve){nt+ct,nx,ny,ng};
		nans+=w[ng];
		nt+=ct;
		while(!pq.empty())pq.pop();
		for(int i=1;i<=n;i++)if(w[i]<nans&&!fl[i])ct=calnt(i,nt),pq.push(make_pair(w[i]/(ct*ct)+G/dis(nx,ny,ax[i]+nt*mx[i],ay[i]+nt*my[i])+rand()%10,i));
	}
	if(nans>aans){
		aans=nans,pans=pa;
		for(int i=1;i<=pa;i++)ans[i]=na[i];
	}
	return nans;
}

Aly_