ABC266D Snuke Panic (1D) 题解

· · 题解

思路分析

考虑 dp。

设 dp_{i,j} 为在第 i 时刻，高桥在 j 位置的答案。

因为每秒高桥只能移动一个位置，所以 dp_{i,j}=\max(dp_{i-1,j-1},dp_{i-1,j},dp_{i-1,j+1})+x，其中 x 表示当前位置 Snuke 的大小，没有 Snuke 则为 0。

代码实现

有几点要注意：

  1. 一开始高桥在 0 位置，所以在第 1 时刻他到不了 2,3,4 的位置，第 2 时刻到不了 3,4 的位置，以此类推。所以在 dp 第二层循环的时候要注意限制一下循环的范围。
  2. 在最后一个 Snuke 出现之后，再跑来跑去已经没有意义了，所以 dp 第一层循环的范围应该是从 1 到 mxt，其中 mxt 为最后一个 Snuke 出现的时间。这个时间可以在输入时维护。
  3. 答案应为 \max\limits_{i=0}^4 dp_{mxt,i}，其中 mxt 为最后一个 Snuke 出现的时间。
  4. 找 x 可以用 lower_bound 找，因为每个时刻最多只会出现一只 Snuke（见数据范围），所以非常方便。

时间复杂度 \mathcal{O}(n\log n)。

#include<algorithm>
#include<cstdio>
#define int long long
using namespace std;
const int maxn=1e5+1;
int n,t[maxn],x[maxn],a[maxn],dp[maxn][5],mxt=0;
signed main(){
    scanf("%lld",&n);
    for(int i=1;i<=n;++i){
        scanf("%lld%lld%lld",&t[i],&x[i],&a[i]);
        mxt=max(t[i],mxt);//统计最后一个Snuke出现的时间。
    }
    for(int i=1;i<=mxt;++i){
        for(int j=0;j<=min(i,4ll);++j){//限制循环范围。
            dp[i][j]=dp[i-1][j];
            if(j>0) dp[i][j]=max(dp[i-1][j-1],dp[i][j]);//dp，注意特判。
            if(j<4) dp[i][j]=max(dp[i-1][j+1],dp[i][j]);
            int pos=lower_bound(t+1,t+1+n,i)-t;//二分找x。
            if(t[pos]==i&&x[pos]==j) dp[i][j]+=a[pos];
        }
    }
    printf("%lld\n",max(max(max(max(dp[mxt][0],dp[mxt][1]),dp[mxt][2]),dp[mxt][3]),dp[mxt][4]));
    return 0;
}

输入似乎是按照 t 值排序的。

因为“中文句子句末不加句号”的奇怪原因被打回了，现在加上了注释的句号。