codeforces-GlobleRound11-C

十月 12, 2020

C. The Hard Work of Paparazzi

题意

给出一个r×r(r<500)的点阵图

n(n<1e6)个明星会分别在ti时刻出现在点(xi,yi)

一个人t=0时刻在(1,1)点,他想和这几个明星相遇(相同时刻在同一地点)

(这几个明星出现的时刻 $t_i$ 严格递增)

每一秒钟他能上下左右移动一个单位在直角坐标范围内

问他最多能与几个人相遇

题解

首先想到这个问题可以用$On^2$ 的dp解决但是n<1e6 需要优化dp的时间复杂度

注意到时间和人数的量级十分大而图的大小最大是500×500 两点之间最远距离为2r-2

于是猜想优化枚举方法是否与2r相关。

有几个事实需要注意到：

对于第i个明星和第j个明星而言一定有$i-j<=t_i-t_j$ 即两人下标差小于等于
对于第i个明星和第j个明星而言一定有$dis(i,j)<2r$ 即两人距离小于2r
若这个人在第i个明星的位置他想要与第j个明星相遇需要满足$dis(i,j)<=t_i-t_j$

于是我们可以得到对于第i个明星和第j个明星若他俩的下标差大于2r

那么这个人一定可以从第i个明星的位置到第j个明星的位置等待第j个明星出现和他相遇

当$i-j<2r$ 时对于i可能存在多个j满足$dis(i,j)<=t_i-t_j$，所以对于i 遍历$j=[i-2r,i)$

当$i-j>=2r$ 时对于i所有属于$[0,i-2r]$区间内的j 都可以转移到i点

(Because the condition $dis(i,j)<=t_i-t_j$ always hold )

即这个人一定可以从第i个明星的位置到第j个明星的位置等待第j个明星出现和他相遇

综上所述：

对于第i个明星,我们需要遍历$j=[i-2r,i)$ 从j转移到i 也要考虑从$j=[0,i-2r]$ 中最优的值转移到i

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define endl '\n'
#define Turnoff std::ios::sync_with_stdio(false)
const int Max=1e5+5;
const ll Mod=1e9+7;
/*
*/
int dp[Max],t[Max],x[Max],y[Max],maxn[Max];
int main(){
    Turnoff;
    int r,n;cin>>r>>n;
    y[0]=x[0]=1;///注意第0时刻他在(1,1)点
    for(int i=1;i<=n;i++)cin>>t[i]>>x[i]>>y[i];
    for(int i=1;i<=n;i++){
        dp[i]=-1e9;//赋值为-inf 若某个点无法到达应该为-inf 而不是0,0表示能到达但不会与任何人相遇
        ///边界i-2r是否遍历不影响因为i-2r一定能转移到i
        for(int L=max(0,i-2*r);L<i;L++){
            if(abs(x[i]-x[L])+abs(y[i]-y[L])<=t[i]-t[L]){
                dp[i]=max(dp[i],dp[L]+1);
                //cout<<i<<" "<<dp[i]<<endl;
            }
        }
        if(i>2*r)dp[i]=max(dp[i],1+maxn[i-2*r]);
        ///这里就是i-j>=2r的情况
        //cout<<i<<" "<<dp[i]<<endl;
        maxn[i]=max(maxn[i-1],dp[i]);
    }
    cout<<maxn[n]<<endl;
}

查看评论

codeforces-GlobleRound11-C

codeforces-GlobleRound11-C

题意

题解