Error message here!

Hide Error message here!

忘记密码?

Error message here!

请输入正确邮箱

Hide Error message here!

密码丢失?请输入您的电子邮件地址。您将收到一个重设密码链接。

Error message here!

返回登录

Close

成绩单

精海臭脚 2020-01-14 20:34:00 阅读数:16 评论数:0 点赞数:0 收藏数:0

Description

期末考试结束了,班主任L老师要将成绩单分发到每位同学手中。L老师共有n份成绩单,按照编号从1到n的顺序叠放在桌子上,其中编号为i的成绩单分数为w_i。成绩单是按照批次发放的。发放成绩单时,L老师会从当叠成绩单中抽取连续的一段,让这些同学来领取自己的成绩单。当这批同学领取完毕后,L老师再从剩余的成绩单中抽取连续的一段,供下一批同学领取。
经过若干批次的领取后,成绩单将被全部发放到同学手中。然而,分发成绩单是一件令人头痛的事情,一方面要照顾同学们的心理情绪,不能让分数相差太远的同学在同一批领取成绩单;
另一方面要考虑时间成本,尽量减少领取成绩单的批次数。对于一个分发成绩单的方案,我们定义其代价为:
其中,k是方案中分发成绩单的批次数,对于第i批分发的成绩单,〖max〗_i是最高分数,〖min〗_i是最低分数。
a,b是给定的评估参数。现在,请你帮助L老师找到代价最小的分发成绩单的方案,并将这个最小的代价告诉L老师
。当然,分发成绩单的批次数k是由你决定的。

 

Input

第一行包含一个正整数n,表示成绩单的数量。
第二行包含两个非负整数a,b,表示给定的评估参数。
第三行包含n个正整数w_i,表示第i张成绩单上的分数。

 

Output

仅一个正整数,表示最小的代价是多少。

 

Sample Input

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

Sample Output

15
【样例数据说明】
第1批:第2至4份成绩单,落差值为1,剩余成绩单为76710712;
第2批:第4份成绩单,落差值为0,剩余成绩单为767712;
第3批:第1至4份成绩单,落差值为1,剩余成绩单为12;
第4批:剩余的2份成绩单,落差值为1。
总代价为4×3+(1^2+0^2+1^2+1^2)×1=15。

HINT

 

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

 

【题解】

令f[i][j][l][r]表示把[i,j]段选得只有值域[l,r]所花最小代价。

转移:

选完表示为f[i][j][0][0],此时枚举k,l,f[i][j][0][0]=min(f[i][j][k][l]+a+b*fang(l-k));

直接选完为a+b*fang(max-min)。

边界条件i==j,如果w[i]在l,r内代价为0;

枚举断点,选择左边取完或右边取完或都不取完。

代码如下:

 

#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