题解 P4072 【[SDOI2016]征途】

· · 题解

题面

想体验更加舒适的体验可以进博客看一下 (博客进去有点慢, 大家体谅一下)

题意体面中写得很明确, 应该不用我说了, 方差的概念在初中人教版九年级数学中有所提到, 没有上过初中的同学们可以左转百度.

将序列拆为几段求最值, 我们考虑用dp来实现.

先推一下式子, 令方差为v, r为某一段路径的长度, \overline r为这m条路径长度的平均数.

则有:

\begin{aligned} v &= \frac{\sum_{i=1}^{m}(\overline r - r_i)^2}{m}\\ &= \frac{\sum_{i=1}^{m}r_i^2 + m * (\overline r)^2 - 2 * (\overline r) * \sum_{i=1}^{m}r_i}{m}\\ &= \frac{\sum_{i=1}^{m}r_i^2 + m * (\frac{\sum_{i=1}^{m}r_i}{m})^2 - 2 * \frac{(\sum_{i=1}^{m}r_i)^2}{m}}{m}\\ &=- \frac{(\sum_{i=1}^{m}r_i)^2}{m ^ 2} + \frac{\sum_{i=1}^{m}r_i^2}{m} \end{aligned}

答案所求为v * m ^ 2, 所以:

\begin{aligned} v * m ^ 2 &= m * \sum_{i=1}^{m}r_i^2 - (\sum_{i=1}^{m}r_i) ^ 2\\ \end{aligned}

我们发现(\sum_{i=1}^{m}r_i) ^ 2是一个定值, 也就是总路径长度的平方, 所以我们只需要求前面那个数就可以了, 用前缀和先处理一下, 即S_i表示1 ~ i的路径的长度.

我们设f[i][k]表示前i段路花k天走的最小花费, 所以我们可以得到状态转移方程:

f[i][k] = min(f[i][k], f[j][k - 1] + (sum[j] - sum[i])^2)

还是老套路, 设对i点选t(t > j)转移比选j转移更优, 则有:

\begin{aligned} f[t][k - 1] + (sum[t] - sum[i])^2 &< f[j][k - 1] + (sum[j] - sum[i]) ^ 2\\ (f[t][k - 1] + sum[t] ^ 2) - (f[j][k - 1] + sum[j] ^ 2) &< 2 * sum[i] * (sum[t] - sum[j])\\ \frac{(f[t][k - 1] + sum[t] ^ 2) - (f[j][k - 1] + sum[j] ^ 2)}{2 * (sum[t] - sum[j])} &< sum[i] \end{aligned}

由此可知道我们需要维护一个上凸包, 不信的话选三个点试一下就可以发现了, 然后愉快的推式子时间又结束了, 下面是大家喜(shen)闻(wu)乐(tong)见(jue)的Coding Time...

代码

#include <iostream>
#include <cstring>
#include <cstdio>
#define N 3005
using namespace std;

int n, m, sum[N], q[N], l, r;
long long f[N], g[N]; 

inline int read()
{
    int x = 0, w = 1;
    char c = getchar();
    while(c < '0' || c > '9') { if (c == '-') w = -1; c = getchar(); }
    while(c >= '0' && c <= '9') { x = x * 10 + c - '0'; c = getchar(); }
    return x * w;
}

bool F_check(int x, int y, int z) { return 1ll * (g[y] - g[x] + sum[y] * sum[y] - sum[x] * sum[x]) < 1ll * 2 * z * (sum[y] - sum[x]); } 

bool S_check(int x, int y, int z) { return (g[y] - g[x] + sum[y] * sum[y] - sum[x] * sum[x]) * (sum[z] - sum[y]) > (g[z] - g[y] + sum[z] * sum[z] - sum[y] * sum[y]) * (sum[y] - sum[x]); }

int main()
{
    n = read(); m = read();
    for(int i = 1; i <= n; i++) { sum[i] = read(); sum[i] += sum[i - 1]; g[i] = 1ll * sum[i] * sum[i]; }
    for(int k = 1; k < m; k++)
    {
        l = 1; r = 0; q[++r] = k; 
        for(int i = k + 1; i <= n; i++)
        {
            while(l < r && F_check(q[l], q[l + 1], sum[i])) l++;
            f[i] = g[q[l]] + 1ll * (sum[i] - sum[q[l]]) * (sum[i] - sum[q[l]]);
            while(l < r && S_check(q[r - 1], q[r], i)) r--;
            q[++r] = i; 
        }
        for(int i = 1; i <= n; i++) g[i] = f[i]; 
    }
    printf("%lld\n", m * f[n] - sum[n] * sum[n]); 
    return 0;
}

不知道交了多少遍才AC的菜鸡我