bzoj4897 [Thu Summer Camp2016]成绩单

传送门：http://www.lydsy.com/JudgeOnline/problem.php?id=4897

【题解】

第一次看这题想的是f[l,r]的区间dp发现仅记录这两个好像不能转移啊

会出现abaca这种情况，也就是拿走的段在原序列中不连续。

考虑为什么会出现这个情况，肯定是这三个a里的元素十分集中，我们才会留着等合并后取。

我们离散值域，记f[l,r,nl,nr]表示[l,r]区间内，剩下[nl,nr]没拿走的min代价。

特别的如果nl=nr=0就表示全拿走了。

那么考虑f[l,r,nl,nr]怎么转移。

首先转移满足区间性质，也就是可以分割，所以

f[l,r,nl,nr]=min(f[l,k,nl,nr]+f[k+1,r,nl,nr], f[l,k,nl,nr]+f[k+1,r,0,0], f[l,k,0,0]+f[k+1,r,nl,nr])

然后考虑f[l,r,0,0]的转移：我要取完这个区间，要么是一次性取完：f[l,r,0,0]=min(f[l,r,0,0], a+b(Max[l..r]-Min[l..r])^2)

要么是留着[x,y]区间，最后取这个区间：f[l,r,0,0] = min(f[l,r,x,y]+a+b(y-x)^2)

然后转移就行啦，复杂度O(n^5)

# include <vector>

# include <stdio.h>

# include <string.h>

# include <iostream>

# include <algorithm>

// # include <bits/stdc++.h>

using namespace std;

typedef long long ll;

typedef long double ld;

typedef unsigned long long ull;

const int M =  + ;

const int mod = 1e9+;

# define RG register

# define ST static

int n, m, A, B, a[M], w[M];

ll f[M][M][M][M];

bool vf[M][M][M][M];

vector<int> ps;

inline ll dp(int l, int r, int nl, int nr) {

    if(vf[l][r][nl][nr]) return f[l][r][nl][nr];

    vf[l][r][nl][nr] = ;

    ll ret = 1e18;

    if(nl ==  && nr == ) {

        int mx = -1e9, mi = 1e9;

        for (int i=l; i<=r; ++i) mx = max(mx, w[i]), mi = min(mi, w[i]);

        f[l][r][][] = A + (ll)B * (ps[mx-]-ps[mi-]) * (ps[mx-]-ps[mi-]);

        for (int i=; i<=m; ++i)

            for (int j=i; j<=m; ++j)

                ret = min(ret, dp(l, r, i, j) + A + (ll)B * (ps[j-]-ps[i-]) * (ps[j-]-ps[i-]));

        return f[l][r][][] = ret;

    }

    if(l == r) {

        if(nl <= w[l] && w[l] <= nr) ret = ;

        return f[l][r][nl][nr] = ret;

    }

    for (int k=l; k<r; ++k) {

        ret = min(ret, dp(l, k, nl, nr) + dp(k+, r, nl, nr));

        ret = min(ret, dp(l, k, nl, nr) + dp(k+, r, , ));

        ret = min(ret, dp(l, k, , ) + dp(k+, r, nl, nr));

    }

    return f[l][r][nl][nr] = ret;

}

int main() {

    cin >> n >> A >> B;

    for (int i=; i<=n; ++i) {

        scanf("%d", a+i);

        ps.push_back(a[i]);

    }

    sort(ps.begin(), ps.end());

    ps.erase(unique(ps.begin(), ps.end()), ps.end());

    m = ps.size();

    for (int i=; i<=n; ++i)

        w[i] = lower_bound(ps.begin(), ps.end(), a[i]) - ps.begin() + ;

    cout << dp(, n, , );

    return ;

}