题目传送门BMOJBZOJ

Description

给你一个数列,每次你可以选择连续的一段,付出 $a+b\times \text{极差}^2$ 的代价将其删去,剩余部分拼到一起成为新的数列继续进行此操作。求将原序列全部删去需要的最小总代价是多少。

Solution

区间dp

对于这种删除连续一段,剩下的拼到一起的问题:把操作对应到原序列上,相当于一些要么包含要么相离的操作。

相离的情况显然是区间dp,设 $f[l][r]$ 表示将原序列的 $[l,r]$ 全部删掉所需的最小总代价。

对于包含的情况,也可以使用区间dp来解决。具体方法是:同时维护转移到一半时的状态。如下图(先删b~c再删a~d):

记录从a转移到b的状态,dp得知bc可以用某代价消掉,进而推知a转移到c的状态,继续转移到d即可。

由于极差之和最大值与最小值有关,因此离散化后设 $g[l][r][i][j]$ 表示将 $[l,r]$ 删至剩下的数最小值为 $i$ ,最大值为 $j$ 的最小代价。

那么每次dp区间 $[l,r]$ ,最后一个位置 r 的转移有两种情况:

1.和前面的 $[l,r-1]$ 放到一起删除,这样的话 r 会影响最小值与最大值,相应的有 $g[l][r][\text{min}(i,w[r])][\max(i,w[r])]=g[l][r-1][i][j] $ ;

2.和后面的某一段 $[k+1,r]$ 作为被包含的子区间删除,这样的话枚举 $k$ ,有 $g[l][r][i][j]=g[l][k][i][j]+f[k+1][r]$ 。
处理完这个区间的 $g[l][r][][]$ 后处理 $f[l][r]$ ,显然依题意有 $f[l][r]=g[l][r][i][j]+a+b\times(j-i)^2$ 。

最后的答案就是 $f[1][n]$ 。

时间复杂度 $O(n^5)$ ,常数极小可以通过。

注意边界问题什么的。

Code

/*
 * @Name: 110766
 * @Author: Lovely_XianShen
 * @Date: 2019-11-03 10:58:41
 * @Aqours!Sunshine!!
 */
#include<bits/stdc++.h>
using namespace std;

int w[55], v[55], f[55][55], g[55][55][55][55];

struct ios {
    inline char read() {
        static const int IN_LEN = 1 << 18 | 1;
        static char buf[IN_LEN], *s, *t;
        return (s == t) && (t = (s = buf) + fread(buf, 1, IN_LEN, stdin)), s == t ? -1 : *s++;
    }

    template <typename _Tp> inline ios &operator >> (_Tp &x) {
        static char c11, boo;
        for (c11 = read(), boo = 0; !isdigit(c11); c11 = read()) {
            if (c11 == -1)return *this;
            boo |= c11 == '-';
        }
        for (x = 0; isdigit(c11); c11 = read())x = x * 10 + (c11^'0');
        boo &&(x = -x);
        return *this;
    }
} io;

inline void gmin(int &x, int y) {
    x > y ? x = y : 0;
}

int main() {
    int n, a, b, len, i, j, k, l, r;
    io >> n >> a >> b;
    for (i = 1 ; i <= n ; i ++ )io >> w[i], v[i] = w[i];
    sort(v + 1, v + n + 1);
    memset(f, 0x3f, sizeof(f)), memset(g, 0x3f, sizeof(g));
    for (i = 1 ; i <= n ; i ++ ) w[i] = lower_bound(v + 1, v + n + 1, w[i]) - v, g[i][i][w[i]][w[i]] = 0, f[i][i] = a;
    for (len = 2 ; len <= n ; len ++ ) {
        for (l = 1 ; l <= n - len + 1 ; l ++ ) {
            r = l + len - 1, g[l][r][w[r]][w[r]] = f[l][r - 1];
            for (i = 1 ; i <= n ; i ++ )
                for (j = i ; j <= n ; j ++ )
                    gmin(g[l][r][min(i, w[r])][max(j, w[r])], g[l][r - 1][i][j]);
            for (k = l ; k < r ; k ++ )
                for (i = 1 ; i <= n ; i ++ )
                    for (j = i ; j <= n ; j ++ )
                        gmin(g[l][r][i][j], g[l][k][i][j] + f[k + 1][r]);
            for (i = 1 ; i <= n ; i ++ )
                for (j = i ; j <= n ; j ++ )
                    gmin(f[l][r], g[l][r][i][j] + a + b * (v[j] - v[i]) * (v[j] - v[i]));
        }
    }
    printf("%d\n", f[1][n]);
    return 0;
}