题解 P5336 【[THUSC2016]成绩单】

T_Q_X · 2020-11-25 14:49:19 · 题解

传送门

洛谷P5336

可能更好的体验

容易发现这是道区间DP题目，于是走流程：

一.定义状态

• 根据答案，考虑 f[l][r] 表示区间 [l,r] 中的成绩单全部被发放需要的最小代价，那么答案就是 f[1][n] 。

• 但是这道题目的发放成绩单方式比较奇妙，发放一段区间可能可以先在区间中随意选择一些部分来发放，再将剩下的部分发放。

• 注意到分发代价只与一段区间中分数的 max 与 min 有关，于是我们令 g[l][r][mn][mx] 为区间 [l,r] 中的所有成绩单发放一部分后剩下的成绩单的分数最大值为 mx ，最小值为 mn 时的最小代价

• 于是有

二.状态转移

• 考虑g[l][r][mn][mx]加入新成绩单 r+1 时的转移：

• 1.保留第r+1张成绩单不取走，未来与 [l,r] 中的成绩单共同取走：

  g[l][r+1][min(mn,w[r+1])][max(mx.w[r+1])] =min(g[l][r][mn][mx])

• 2.枚举 k，将 [r+1,k] 这段区间的成绩单共同取走

  g[l][k][mn][mx]=min(g[l][r][mn][mx]+f[r+1][k])

• 注意到第一个转移是填表，第二个转移是刷表

• 于是将第二个转移稍微变化一下变化成

  g[l][r][mn][mx]=min(g[l][k][mn][mx]+f[k+1][r])

• 再在区间DP枚举len时从1开始枚举即可

三、代码

#include<bits/stdc++.h>
using namespace std;
const int N=55;
int n,a,b,w[N],f[N][N],g[N][N][N][N],d[N];
int tot;
int main(){
    scanf("%d%d%d",&n,&a,&b);
    for(int i=1;i<=n;++i) scanf("%d",&w[i]),d[i]=w[i];
    sort(d+1,d+n+1);tot=unique(d+1,d+n+1)-d-1;
    for(int i=1;i<=n;++i) w[i]=lower_bound(d+1,d+tot+1,w[i])-d,f[i][i]=a;
    memset(g,0x3f,sizeof(g));memset(f,0x3f,sizeof(f));
    for(int i=1;i<=n;++i)g[i][i][w[i]][w[i]]=0;
    for(int len=1;len<=n;++len)
        for(int l=1,r=len;r<=n;++l,++r)
            for(int mn=1;mn<=tot;++mn)
                for(int mx=mn;mx<=tot;++mx){
                    int &G=g[l][r][mn][mx];
                    for(int k=l;k<r;++k)    G=min(g[l][k][mn][mx]+f[k+1][r],G);
                    int &gg=g[l][r+1][min(mn,w[r+1])][max(mx,w[r+1])];
                    gg=min(gg,G);f[l][r]=min(f[l][r],G+a+b*(d[mx]-d[mn])*(d[mx]-d[mn]));
                }
    printf("%d\n",f[1][n]);
}