P2285打鼹鼠题解

cxm1024 · 2021-09-05 10:22:49 · 个人记录

更好的阅读体验

基础的DP各位大佬已经讲得很明白了，本文主要讲一讲优化

DP状态很容易想到：f[i] 表示打完第 i 只鼹鼠能获得的最多数量。

转移：f[i]=\min\limits_{j<i,\ t[i]-t[j]>=dis(i,j)}f[j]+1，即对于每一个打完第 j 个能来得及走到第 i 个的 j，算最大的 f[j]+1。

重点来了！！

优化

我们发现，如果时间差大于 2\times n，无论在~~天涯海角~~哪里都能走到，又因为输入的时间是升序排列，我们只需要在转移时维护 g[i] 表示 \max\limits_{j<=i}f[i]，这样在转移 f[i] 时就可以先用 start=upper\_bound-1 找出最后一个“时间差大于 2\times n” 的鼹鼠，他前面的鼹鼠无论多远都能到达，就可以直接用 g[start] 来代替，枚举时就只需要从 start 开始枚举了。

#include<bits/stdc++.h>
using namespace std;
int t[10010],x[10010],y[10010];
int f[10010],g[10010];
int dis(int a,int b) {
    return abs(x[a]-x[b])+abs(y[a]-y[b]);
}
int main() {
    int n,m;
    scanf("%d%d",&n,&m);
    for(int i=1;i<=m;i++)
        scanf("%d%d%d",&t[i],&x[i],&y[i]);
    for(int i=1;i<=m;i++) {
        int start=max(0,int(upper_bound(t+1,t+i,t[i]-2*n)-t-1));
        f[i]=g[start]+1;
        for(int j=max(1,start);j<i;j++) {
            if(t[i]-t[j]>=dis(i,j))
                f[i]=max(f[i],f[j]+1);
        }
        g[i]=max(g[i-1],f[i]);
    }
    printf("%d\n",g[m]);
    return 0;
}

哎哎哎，别急着走，后面还有：

继续优化

我们发现，由于时间是递增的，所以 i 的 start 一定不会小于 i-1 的 start，所以我们用 start[i] 记录第 i 只鼹鼠的 start，那么 upper\_bound 时就只需要从 start[i-1] 开始查找。

#include<bits/stdc++.h>
using namespace std;
int t[10010],x[10010],y[10010];
int f[10010],g[10010],start[10010];
int dis(int a,int b) {
    return abs(x[a]-x[b])+abs(y[a]-y[b]);
}
int main() {
    int n,m;
    scanf("%d%d",&n,&m);
    for(int i=1;i<=m;i++)
        scanf("%d%d%d",&t[i],&x[i],&y[i]);
    for(int i=1;i<=m;i++) {
        start[i]=max(0,int(upper_bound(t+start[i-1],t+i,t[i]-2*n)-t-1));
        f[i]=g[start[i]]+1;
        for(int j=max(1,start[i]);j<i;j++) {
            if(t[i]-t[j]>=dis(i,j))
                f[i]=max(f[i],f[j]+1);
        }
        g[i]=max(g[i-1],f[i]);
    }
    printf("%d\n",g[m]);
    return 0;
}

哎哎哎，别急着走，后面还有：

继续继续优化

我们甚至可以直接不用 upper\_bound 和 start 数组了（没错），开一个变量 start，维护当前的 start，转移之前用一个

for(;t[i]-t[start+1]>=2*n;start++);

来更新 start，可以发现，整个程序运行下来，start 最多只会更新 n次，所以复杂度可忽略。

最终代码：

#include<bits/stdc++.h>
using namespace std;
int t[10010],x[10010],y[10010];
int f[10010],g[10010],start;
int dis(int a,int b) {
    return abs(x[a]-x[b])+abs(y[a]-y[b]);
}
int main() {
    int n,m;
    scanf("%d%d",&n,&m);
    for(int i=1;i<=m;i++)
        scanf("%d%d%d",&t[i],&x[i],&y[i]);
    for(int i=1;i<=m;i++) {
        for(;t[i]-t[start+1]>=2*n;start++);
        f[i]=g[start]+1;
        for(int j=max(1,start);j<i;j++) {
            if(t[i]-t[j]>=dis(i,j))
                f[i]=max(f[i],f[j]+1);
        }
        g[i]=max(g[i-1],f[i]);
    }
    printf("%d\n",g[m]);
    return 0;
}

不开O2可达48ms，可见优化非常显著。

请勿抄袭，如果一定要抄，请理解明白后再抄

P2285打鼹鼠 题解

重点来了！！

P2285打鼹鼠题解