P1915 [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}

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

​ 目标变为求最优的排列 \{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;
}