Blog of RuSun

\begin {array}{c} \mathfrak {One Problem Is Difficult} \\\\ \mathfrak {Because You Don't Know} \\\\ \mathfrak {Why It Is Diffucult} \end {array}

P4767 [IOI2000]邮局

发表于 分类于
本文字数： 4.7k 阅读时长 ≈ 4 分钟
标签：        

P4767 [IOI2000]邮局

先考虑暴力。

$f _ {i, j}$ 表示使用 $i$ 个邮局，前 $j$ 个村庄的答案。对于一段村庄选择一个邮局，如果村庄的个数为奇数，那么选择中间的数；否则为中间两个数中任意一数。即对于 $[l, r]$ ，$mid = \left \lfloor \frac {l + r} 2 \right \rfloor $ 。那么距离和
$$
\begin {aligned}
w _ {l, r} & = \sum _ {i = l} ^ {mid} d _ {mid} - d _ i + \sum _ {i = mid + 1} ^ r d _ i - d _ {mid} \\
& = (mid - l + 1) d _ {mid} - (s _ {mid} - s _ {l - 1}) + (s _ r - s _ {mid}) - (r - mid) d _ {mid} \\
& = (2 mid - l - r + 1) d _ {mid} + s _ r + s _ {l - 1} - 2 s _ {mid} \\
\end {aligned}
$$
注意到 $2mid$ 和 $l + r$ 的关系，如果 $mid = \frac {l + r} 2$ ，那么
$$
w _ {l, r} = s _ r + s _ {l - 1} - 2 s _ {mid} + d _ {mid}
$$
否则
$$
w _ {l, r} = s _ r + s _ {l - 1} - 2 s _ {mid}
$$

查看代码 
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
36
37
38
#include <cstdio>
#include <algorithm>
using namespace std;
const int N = 310, inf = 1e9;
int n, m, d[N], s[N], f[2][N], g[2][N];
int main()
{
    scanf("%d%d", &n, &m);
    for (int i = 1; i <= n; i++)
    {
        scanf("%d", &d[i]);
        s[i] = s[i - 1] + d[i];
    }
    for (int i = 1; i <= n; i++)
        f[0][i] = inf;
    for (int i = 1; i <= m; i++)
    {
        for (int j = 1; j <= i; j++)
            printf("\t");
        for (int j = 0; j <= n; j++)
        {
            f[i & 1][j] = inf;
            for (int k = 0; k < j; k++)
            {
                int mid = j + k >> 1;
                if (f[i - 1 & 1][k] + (mid - k) * d[mid] - (s[mid] - s[k]) + (s[j] - s[mid]) - (j - mid) * d[mid] < f[i & 1][j])
                {
                    g[i & 1][j] = k;
                    f[i & 1][j] = f[i - 1 & 1][k] + s[j] + s[k] - s[mid] * 2 + ((j + k & 1) ? d[mid] : 0);
                }
            }
            printf("%d\t", i, j, g[i & 1][j]);
        }
        puts("");
    }
    printf("%d", f[m & 1][n]);
    return 0;
}

暴力打表发现决策具有单调性。

现在考察 $w$ 是否满足四边形不等式。

若 $mid = \frac {l + r - 1} 2$ 。那么
$$
w _ {l, r} = s _ r + s _ {l - 1} - 2 s _ {mid}
$$

$$
w _ {l + 1, r} = s _ r + s _ {l} - 2 s _ {mid + 1} + d _ {mid + 1}
$$

$$
w _ {l, r + 1} = s _ {r + 1} + s _ {l - 1} - 2 s _ {mid + 1} + d _ {mid + 1}
$$

$$
w _ {l + 1, r + 1} = s _ {r + 1}+ s _ {l} - 2 s _ {mid + 1}
$$

要证 $w _ {l, r} + w _ {l + 1, r + 1} \le w _ {l + 1, r} + w _ {l, r + 1}$ ，只需证

$$
s _ r + s _ {l - 1} - 2 s _ {mid} + s _ {r + 1}+ s _ {l} - 2 s _ {mid + 1} \le s _ r + s _ {l} - 2 s _ {mid + 1} + d _ {mid + 1} + s _ {r + 1} + s _ {l - 1} - 2 s _ {mid + 1} + d _ {mid + 1}
$$

即

$$
-2 s _ {mid} \le - 2 s _ {mid + 1} + d _ {mid + 1} + d _ {mid + 1}
$$

即

$$
0 \le 0
$$

显然成立，故四边形不等式成立。

若 $mid = \frac {l + r} 2$ ，则
$$
w _ {l, r} = s _ {l - 1} + s _ r - 2 s _ {mid} + d _ {mid}
$$

$$
w _ {l + 1, r} = s _ {l} + s _ r - 2 s _ {mid}
$$

$$
w _ {l, r + 1} = s _ {l - 1} + s _ {r + 1} - 2 s _ {mid}
$$

$$
w _ {l + 1, r + 1} = s _ {l} + s _ {r + 1} - 2 s _ {mid + 1} + d _ {mid + 1}
$$

要证 $w _ {l, r} + w _ {l + 1, r + 1} \le w _ {l + 1, r} + w _ {l, r + 1}$ ，只需证
$$
s _ {l - 1} + s _ r - 2 s _ {mid} + d _ {mid} + s _ {l} + s _ {r + 1} - 2 s _ {mid + 1} + d _ {mid + 1} \le s _ {l} + s _ r - 2 s _ {mid} + s _ {l - 1} + s _ {r + 1} - 2 s _ {mid}
$$
即
$$
d _ {mid} - 2 s _ {mid + 1} + d _ {mid + 1} \le -2 s _ {mid}
$$
即
$$
d _ {mid} \le d _ {mid + 1}
$$
成立。

综上， $w$ 满足四边形不等式。

$\forall a \le b \le c \le d, w(a, d) \ge w(b, c)$ 显然成立。

故，$f$ 满足四边形不等式。

查看代码 
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
#include <cstdio>
#include <algorithm>
using namespace std;
const int N = 3e4 + 10, inf = 1e9;
int n, m, d[N], s[N], f[2][N], g[2][N];
int main()
{
    scanf("%d%d", &n, &m);
    for (int i = 1; i <= n; i++)
    {
        scanf("%d", &d[i]);
        s[i] = s[i - 1] + d[i];
    }
    for (int i = 1; i <= n; i++)
        f[0][i] = inf;
    for (int i = 1; i <= m; i++)
    {
        g[i & 1][n + 1] = n - 1;
        for (int j = n; j > 0; j--)
        {
            f[i & 1][j] = inf;
            for (int k = g[i - 1 & 1][j]; k <= g[i & 1][j + 1]; k++)
            {
                int mid = j + k + 1 >> 1;
                if (f[i - 1 & 1][k] + (mid - k) * d[mid] - (s[mid] - s[k]) + (s[j] - s[mid]) - (j - mid) * d[mid] < f[i & 1][j])
                {
                    g[i & 1][j] = k;
                    f[i & 1][j] = f[i - 1 & 1][k] + s[j] + s[k] - s[mid] * 2 + ((j + k & 1) ? d[mid] : 0);
                }
            }
        }
    }
    printf("%d", f[m & 1][n]);
    return 0;
}
相关文章