Loj#2292.「THUSC 2016」成绩单 题解

题意：

• 略。

题解：

• 考虑用 $f[l][r][i][j]$ 表示区间 $[l,r]$，最后一次取的目前最大值为 $i$，最小值为 $j$ 除最后一次的最小总代价。
• $g[l][r]$ 表示取完区间 $[l,r]$ 的最小总代价。
• 有两种转移：
  • 将 $f[l][r][i][j]$ 最后一次取的完成：$g[l][k]=\min(g[l][k],f[l][r][i][j]+g[r+1][k]+a+b\times (i-j)^2)$。
  • 将 $f[l][r][i][j]$ 新扩展一次：$f[l][k][\max(i,w[k])][\min(j,w[k])]=\min(f[l][k][\max(i,w[k])][\min(j,w[k])],f[l][r][i][j]+g[r+1][k])$。
• 然后离散化一下权值。
• 时间复杂度 $O(n^4)$。

代码：

#include <bits/stdc++.h>
#define gc getchar()
using namespace std;
const int N=59;
int a[N],n,val[N],A,B,f[N][N][N][N],g[N][N];
vector<int> q;
int read()
{
    int x=1;
    char ch;
    while (ch=gc,ch<'0'||ch>'9') if (ch=='-') x=-1;
    int s=ch-'0';
    while (ch=gc,ch>='0'&&ch<='9') s=s*10+ch-'0';
    return s*x;
}
void up(int &x,int y)
{
    x=min(x,y);
}
int main()
{
    n=read(),A=read(),B=read();
    for (int i=1;i<=n;i++) a[i]=read(),q.push_back(a[i]);
    sort(q.begin(),q.end());
    q.erase(unique(q.begin(),q.end()),q.end());
    for (int i=1;i<=n;i++)
        a[i]=lower_bound(q.begin(),q.end(),a[i])-q.begin()+1;
    memset(f,63,sizeof(f)),memset(g,63,sizeof(g));
    for (int i=1;i<=n;i++)
        f[i][i][a[i]][a[i]]=0,g[i+1][i]=0;
    g[1][0]=0;
    for (int l=n;l;--l)
        for (int r=l;r<=n;++r)
            for (int i=1;i<=n;i++)
                for (int j=1;j<=i;j++)
                {
                    if (f[l][r][i][j]==0x3f3f3f3f) continue;
                    for (int k=r+1;k<=n;k++)
                        up(f[l][k][max(i,a[k])][min(j,a[k])],f[l][r][i][j]+g[r+1][k-1]);
                    for (int k=r;k<=n;k++)
                        up(g[l][k],f[l][r][i][j]+g[r+1][k]+A+B*(q[i-1]-q[j-1])*(q[i-1]-q[j-1]));
                }
    printf("%d\n",g[1][n]);
    return 0;
}