死亡鸽者

Posted on Edited on In

题目大意：现在有N座城市排成一排， 死亡鸽者会从第一座城市一直走到最后一座城市。 每个城市都有一个数\(a_i\)， 每次死亡鸽者可以选择取走或者不取走这个数， 但想要取走这个数的话要求这个数必须是所有已经取走的数的倍数或者约数。现在问死亡鸽者从第一座城市走到最后一座城市的过程中， 最多取走多少个数。

1e6的数据量，很容易的想到开个桶与筛法

我们设\(f[i]\)表示以i为结尾的序列最长有多长，显然，\(f[i]\)是有i的比i小的数转移过来的，

现在取出的是i，那么之后的都是i的倍数

\(f[k\times i] = max(f[i]+cnt[k\times i])\)

代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
#define int long long
using namespace std;
const int N = 1e6 + 66;

int n;
int f[N], cnt[N];

signed main()
{
    int i, j;
    n = read();
    for (i = 1; i <= n; ++ i)
    {
        int x = read();
        ++ cnt[x], ++ f[x];
    }
    int res = 0;
    
    for (i = 1; i <= 1000000; ++ i)
    {
        if (f[i])
        {
            if (f[i] > res) res = f[i];
            for (j = i + i; j <= 1000000; j += i)
            {
                if (cnt[j] && f[i] + cnt[j] > f[j])
                {
                    f[j] = f[i] + cnt[j];
                }
            }
        }
    }
    put(res);
    return 0;
}

总结：

这次考试期望得分是100+20+20pts，但实际得分10+20+20pts

正解写挂了，但是我暴力分数拿满了，我知道我有进步，暴力分数拿满意味着，至少我没有亏负两道题

但是第一题正解挂了九十分就很烦人

我要继续努力，在保证暴力分数拿满的基础上，签到题目必须切掉