HDU 2829 题解

admin 2021-10-09 PM 29℃ 0条

题目链接

题意

给定 $n$ 个数 $a_1,a_2,\ldots a_n$,将这些数分成连续的 $m$ 段,使得每一段中的数两两乘积之和最小。求最小值。

分析

显然的朴素 DP:设 $dp_{i,j}$ 表示将前 $i$ 个数分成 $j$ 段,每一段中的数两两乘积总和的最小值。

则 $dp_{i,j}=\min\{dp_{k-1,j-1}+w(k,i)\},k=1,2,\ldots i-1$。其中 $w(k,i)$ 为 $a_k$ 到 $a_i$ 之间两两的乘积之和。

这样的时间复杂度是 $O(n^2m)$ 的,考虑优化。

方法 1:四边形不等式优化

显然 $w$ 具有区间包含单调性且满足四边形不等式(随便减一下就行)。可以用四边形不等式优化。

代码非常的好写,但是要注意边界情况。

方法 2:斜率优化

众所周知,交叉积等于和的平方与平方和的差的一半。

设 $s$ 为 $a$ 的前缀和,$sq$ 为 $a$ 的平方前缀和。

$$dp_{k-1,j-1}+w(k,i)>dp_{l-1,j-1}+w(l,i)$$

$$dp_{k-1,j-1}+\dfrac{(s_i-s_{k-1})^2-(sq_i-sq_{k-1})}{2}>dp_{l-1,j-1}+\dfrac{(s_i-s_{l-1})^2-(sq_i-sq_{l-1})}{2}$$

当且仅当

$$(dp_{k-1,j-1}+\dfrac{s_{k-1}^2+sq_{k-1}}{2})-(dp_{l-1,j-1}+\dfrac{s_{l-1}^2+sq_{l-1}}{2})>s_i(s_{k-1}-s_{l-1})$$

设 $X(i)=s_{i-1}$,$Y(i)=dp_{i-1,j-1}+\dfrac{s_{i-1}^2+sq_{i-1}}{2}$。

则从 $k$ 转移到 $i$ 劣于从 $l$ 转移到 $i$,当且仅当

$$\dfrac{Y(k)-Y(l)}{X(k)-X(l)}>s_i$$

其实并不需要开很多个队列,只需要先枚举 $j$ 再枚举 $i$ 即可。

解决

只保证下面代码能在 g++ 9.3.0 / clang++ 10.0.0 C++14 64 bit 标准下编译通过。

不保证不会在 HDU 上 CE。

方法 1

#include <algorithm>
#include <cmath>
#include <cstdio>
#include <cstring>
#include <iostream>

using namespace std;
using LL = long long;
using LLL = __int128;

const int _ = 1005;
int n, m, pos[_][_], a[_];
LL dp[_][_], w[_][_];

int main()
{
    while (~scanf("%d%d", &n, &m) && n + m)
    {
        m++;
        for (int i = 1; i <= n; i++)
        {
            scanf("%d", &a[i]);
            w[i][i] = 0;
        }
        for (int i = 1; i <= n; i++)
        {
            LL sum = a[i];
            for (int j = i + 1; j <= n; j++)
            {
                w[i][j] = w[i][j - 1] + a[j] * sum;
                sum = sum + a[j];
            }
        }
        for (int i = 1; i <= n; i++)
            dp[i][1] = w[1][i], pos[i][1] = 1;
        for (int j = 2; j <= m; j++)
        {
            pos[n + 1][j] = n;
            for (int i = n; i >= 1; i--)
            {
                dp[i][j] = 1e10;
                for (int k = pos[i][j - 1]; k <= pos[i + 1][j]; k++)
                    if (dp[k - 1][j - 1] + w[k][i] < dp[i][j])
                        dp[i][j] = dp[k - 1][j - 1] + w[k][i], pos[i][j] = k;
            }
        }
        printf("%lld\n", dp[n][m]);
    }
    return 0;
}
标签: none

非特殊说明,本博所有文章均为博主原创。

上一篇 CF 631E 题解
下一篇 没有了

评论啦~