P5336

· · 个人记录

[THUSC2016]成绩单

区间 DP。

我一开始想了一个奇怪的做法，定义 f(i,j,k) 表示区间 [i,j] 取了 k 次，然后不行。fcy 一下就看出了状态的问题，显然可以在 [i,j] 中取多个不相同不相邻的区间，然后把剩下的一起取掉。我 tcl。

我们定义状态 f(i,j,l,r) 表示区间 [i,j] 在取过若干次之后，剩余的最小值为 l，最大值为 r 的最大价值。再定义 g(i,j) 表示区间 [i,j] 取完的最小代价。

然后我们发现这个转移似乎只在 f 之间会比较困难，所以借助 g 转移：

f(i,j,l,r)=\min_{k\in [i,j)}\{f(i,p,l,r)+g(k+1,j)\}

但借助 g 转移显然就说明这一段要被全取完，显然会漏掉一种最后一段可能有若干个空着没取的情况，所以我们还要再添加一个转移：

f(i,j,\min\{l,w_j\},\max\{r,w_j\})=\min\{f(i,j-1,l,r)\}

这样就可以接起来了。

最后处理 g(i,j)，可以直接 g(i,j)=\min_{l\le r\in W}\{f(i,j,l,r)+a+b(r-l)^2\}。

关于初始化，直接处理长度为 1 的区间即可，即 f(i,i,w_i,w_i)=0，g(i,i)=a。

显然 w_i 需要离散化。

时间复杂度 O(n^5)。

代码：

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#define ll long long
using namespace std;

const ll N=50;

ll n,a,b,totw;

ll g[N+5][N+5],f[N+5][N+5][N+5][N+5];

ll w[N+5],uqw[N+5];

inline ll read() {
    ll ret=0,f=1;char ch=getchar();
    while(ch<'0'||ch>'9') {if(ch=='-') f=-f;ch=getchar();}
    while(ch>='0'&&ch<='9') {ret=(ret<<3)+(ret<<1)+ch-'0';ch=getchar();}
    return ret*f;
}

void write(ll x) {
    static char buf[22];static ll len=-1;
    if(x>=0) {
        do{buf[++len]=x%10+48;x/=10;}while(x);
    }
    else {
        putchar('-');
        do{buf[++len]=-(x%10)+48;x/=10;}while(x);
    }
    while(len>=0) putchar(buf[len--]);
}

int main() {

    n=read();

    a=read();b=read();

    memset(f,0x3f,sizeof(f));memset(g,0x3f,sizeof(g));
    for(ll i=1;i<=n;i++) {
        w[i]=read();uqw[++totw]=w[i];
    }
    sort(uqw+1,uqw+totw+1);totw=unique(uqw+1,uqw+totw+1)-uqw-1;
    for(ll i=1;i<=n;i++) {
        w[i]=lower_bound(uqw+1,uqw+totw+1,w[i])-uqw;
        f[i][i][w[i]][w[i]]=0;g[i][i]=a;
    }

    for(ll i=2;i<=n;i++) {
        for(ll j=1;j+i-1<=n;j++) {
            for(ll l=1;l<=totw;l++) {
                for(ll r=l;r<=totw;r++) {
                    f[j][j+i-1][min(l,w[j+i-1])][max(r,w[j+i-1])]=
                    min(f[j][j+i-1][min(l,w[j+i-1])][max(r,w[j+i-1])],
                    f[j][j+i-2][l][r]);
                    for(ll k=j;k<j+i-1;k++) {
                        f[j][j+i-1][l][r]=min(f[j][j+i-1][l][r],
                        f[j][k][l][r]+g[k+1][j+i-1]);
                    }
                }
            }
            for(ll l=1;l<=totw;l++) {
                for(ll r=l;r<=totw;r++) {
                    g[j][j+i-1]=min(g[j][j+i-1],
                    f[j][j+i-1][l][r]+a+b*(uqw[r]-uqw[l])*(uqw[r]-uqw[l]));
                }
            }
        }
    }

    write(g[1][n]);

    return 0;
}