题目描述
给你一个数列，每次你可以选择连续的一段，付出 $a+b imes 极差^2$ 的代价将其删去，剩余部分拼到一起成为新的数列继续进行此操作。求将原序列全部删去需要的最小总代价是多少。
输入
第一行包含一个正整数n，表示成绩单的数量。
第二行包含两个非负整数a,b，表示给定的评估参数。
第三行包含n个正整数w_i，表示第i张成绩单上的分数。
输出
仅一个正整数，表示最小的代价是多少。
样例输入
10
3 1
7 10 9 10 6 7 10 7 1 2
样例输出
15
题解
区间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$ 的转移有两种情况：
- 和前面的 $[l,r-1]$ 放到一起删除，这样的话 $r$ 会影响最小值与最大值，相应的有 $g[l][r][ ext{min}(i,w[r])][ ext{max}(i,w[r])]=g[l][r-1][i][j]$ ；
- 和后面的某一段 $[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 imes(j-i)^2$ 。
最后的答案就是 $f[1][n]$ 。
时间复杂度 $O(n^5)$ ，常数极小可以通过。
注意边界问题什么的。
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
int w[52] , v[52] , f[52][52] , g[52][52][52][52];
inline void gmin(int &x , int y)
{
x > y ? x = y : 0;
}
int main()
{
int n , a , b , len , i , j , k , l , r;
scanf("%d%d%d" , &n , &a , &b);
for(i = 1 ; i <= n ; i ++ ) scanf("%d" , &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
" , f[1][n]);
return 0;
}