CF283D

· · 个人记录

link
这是一道非常有趣的题目：
题意： 对于一个序列 a_i ,修改最少的位置使得 \forall i \in [1, n - 1] a_i， 可以表示为 a_{i + 1} 个数字的和。

我们先考虑对于一组满足要求的数字 (x, y), x, y 之间满足什么关系:

x = \frac{y(y - 1)}{2} + ky \frac{2x}{y} - y = 2k - 1

所以 \frac{2x}{y} - y = 2k - 1 是奇数， 有奇偶性， 我们考虑把数字表示成 2 ^ {v(x)} * p(x) 的形式
即

2 ^ {v(x) + 1 - v(y)} * \frac{p(x)}{p(y)} - y

首先， 要满足 p(y) | p(x)

然后， 进行分类讨论

1.\ y = 2k + 1, \ (k \in \Z), \ v(y) = 0, \ v(x)任意\\ 2. \ y = 2k, \ (k \in \Z), \ v(y) = v(x) + 1

然后，进行 DP 

for (int i = 1; i <= n; i++) {
        f[i] = i - 1;
        for (int j = 1; j < i; j++) {
            if (p[j] % p[i] != 0) continue;
            if (v[i] == v[j] + i - j || v[i] <= i - j - 1) f[i] = min(f[i], f[j] + i - j - 1);
        }
        ans = min(ans, f[i] + n - i);
    }