Error message here!

Hide Error message here!

Error message here!

Hide Error message here!

Error message here!

Close

## Description

a,b是给定的评估参数。现在，请你帮助L老师找到代价最小的分发成绩单的方案，并将这个最小的代价告诉L老师
。当然，分发成绩单的批次数k是由你决定的。

## Sample Input

10
3 1
7 10 9 10 6 7 10 7 1 2

15
【样例数据说明】

## HINT

n<=50, a<=100, b<=10, w_i<=1000

【题解】

```#include<bits/stdc++.h>
using namespace std;
int n,a,b,w[],f[][][][],dui[],cnt;
bool book[][][][];
struct lisan
{
int zhi,id;
}ls[];
inline bool cmp(lisan x,lisan y)
{
return x.zhi<y.zhi;
}
inline int fang(int x)
{
return x*x;
}
inline int dfs(int i,int j,int x,int y)
{
if(book[i][j][x][y]) return f[i][j][x][y];
book[i][j][x][y]=;
f[i][j][x][y]=99999999;
if(!x&&!y)
{
int mx=-,mi=9999999;
for(int k=i;k<=j;k++) mx=max(mx,dui[w[k]]),mi=min(mi,dui[w[k]]);
f[i][j][x][y]=a+b*fang(mx-mi);
for(int k=;k<=cnt;k++)
for(int l=k;l<=cnt;l++)
{
int huan=dfs(i,j,k,l);
f[i][j][x][y]=min(f[i][j][x][y],huan+a+b*fang(dui[l]-dui[k]));
}
return f[i][j][x][y];
}
else
{
if(i==j)
{
if(x<=w[i]&&w[i]<=y) f[i][j][x][y]=;
return f[i][j][x][y];
}
for(int k=i;k<j;k++)
{
f[i][j][x][y]=min(f[i][j][x][y],dfs(i,k,x,y)+dfs(k+,j,x,y));
f[i][j][x][y]=min(f[i][j][x][y],dfs(i,k,,)+dfs(k+,j,x,y));
f[i][j][x][y]=min(f[i][j][x][y],dfs(i,k,x,y)+dfs(k+,j,,));
}
return f[i][j][x][y];
}
}
int main()
{
cin>>n>>a>>b;
for(int i=;i<=n;i++) cin>>ls[i].zhi,ls[i].id=i;
sort(ls+,ls+n+,cmp);ls[].zhi=-;
for(int i=;i<=n;i++)
{
if(ls[i].zhi!=ls[i-].zhi) cnt++;
w[ls[i].id]=cnt;dui[cnt]=ls[i].zhi;
}
cout<<dfs(,n,,);
}```
View Code

https://www.cnblogs.com/betablewaloot/p/12193965.html