P2285打鼹鼠 题解

发表于 更新于 分类于

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

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

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

重点来了！！

优化

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
#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;
}

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

继续优化

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
#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;
}

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

继续继续优化

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

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

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

最终代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
#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，可见优化非常显著。

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