摘樱桃

【题目描述】

n个樱桃排成一列,第i个樱桃的甜度为v[i],你要把n个樱桃分成若干组,其中每一组的樱桃必须相邻。每一组樱桃的美味度为(sum-T)^2 , 其中sum是这组樱桃的甜度之和,T为输入给定的系数。

一组方案的美味度为每一组的美味度之和。

求可行方案最小的美味度。

【输入格式】

输入文件cherry.in

第一行两个正整数 n,T。

第二行n个整数,第i个整数是第i个樱桃的甜度,v[i]。

【输出格式】

输出文件cherry.out

一行一个非负整数,为最小美味度。

【样例输入】

5 5

3 5 2 1 6

【样例输出】

【数据范围】

对于50%的数据满足 n<=10,T<=1000,v[i]<=10

对于70%的数据满足 n<=100

对于所有数据,n<=10^3,T<=1000,v[i]<=10

每组樱桃必须相邻,使美味度之和最小。很容易联想到其实和石子合并差不多,可以用区间划分来做。但是看一眼数据1000,n3的复杂度,应该会tle(事实证明就是会T了)。

那么应该怎么样优化呢,我们可以考虑,不采用区间划分,我们枚举有多少个樱桃,然后再枚举这个樱桃和最后几个樱桃组成一组。

具体实现的话,我们要整一个前缀和(求甜度要用),我们可以用f【i】表示前i个樱桃的最少甜度那么,用j来枚举与第i个樱桃组成一组的樱桃的数量的开始,那么状态转移方程就出来了

f[i]=min(f[i],f[j]+(sum[i]-sum[j-1]-t)*(sum[i]-sum[j-1]-t));

最后附上代码

 

 1 #include<cstdio>
 2 #include<iostream>
 3 #include<cstring>
 4 using namespace std;
 5 int n,a[1010],f[1010],t,sum[1010];
 6 int main()
 7 {
 8     scanf("%d%d",&n,&t);
 9     memset(f,0x3f,sizeof(f));
10     for(int i=1;i<=n;++i)
11     {
12         scanf("%d",&a[i]);
13         sum[i]=sum[i-1]+a[i];
14     }
15     
16     f[1]=(a[1]-t )*(a[1]-t);
17     f[0]=0;
18     for(int i=2;i<=n;++i)
19     {
20         for(int j=i-1;j>=0;--j)
21         {
22             f[i]=min(f[i],f[j]+(sum[i]-sum[j]-t)*(sum[i]-sum[j]-t));
23         }
24     }
25     printf("%d",f[n]);
26     return 0;
27 }

 

 

 

 

 

 

全部评论

相关推荐

08-27 12:02
已编辑
南京外国语学校 网络安全
再来一遍:实则劝各位不要all in华子,不要相信华为hr
点赞 评论 收藏
分享
08-21 16:35
已编辑
门头沟学院 Java
点赞 评论 收藏
分享
10-13 22:56
门头沟学院 C++
rt,鼠鼠的浪潮网签明天过期,鼠鼠是山东人,好像自己也能接受。之前的面试大厂基本挂干净了,剩下小米二面后在泡,问了下面试官没有挂,但要泡。还有海信似乎也通过了,不过在深圳,鼠鼠也不是很想去。其它还有一些公司应该陆陆续续还有一些面试,现在有些纠结是直接签了还是再等再面呢?大佬们能不能给鼠鼠提一些意见,万分感谢!!!
牛客78696106...:浪潮可不是开摆,当初我还是开发的时候我组长跟我说他们组有段时间天天1,2点走,早上5点就来,全组肝出来心肌炎,浪潮挣钱省立花可不是说说,当然也看部门,但是浪潮普遍就那dio样,而且你算下时薪就知道不高,没事也是9点半走,不然算你旷工
投递小米集团等公司10个岗位
点赞 评论 收藏
分享
评论
点赞
收藏
分享

创作者周榜

更多
牛客网
牛客网在线编程
牛客网题解
牛客企业服务