博客
关于我
强烈建议你试试无所不能的chatGPT,快点击我
Partial Sum
阅读量:5759 次
发布时间:2019-06-18

本文共 1757 字,大约阅读时间需要 5 分钟。

Partial Sum

Accepted : 80   Submit : 353
Time Limit : 3000 MS   Memory Limit : 65536 KB 

 

Partial Sum

Bobo has a integer sequence a1,a2,,an of length n . Each time, he selects two ends 0l<rn and add |rj=l+1aj|C into a counter which is zero initially. He repeats the selection for at most m times.

If each end can be selected at most once (either as left or right), find out the maximum sum Bobo may have.

Input

The input contains zero or more test cases and is terminated by end-of-file. For each test case:

The first line contains three integers n, m, C . The second line contains integers a1,a2,,an .

  • 2n105
  • 12mn+1
  • |ai|,C104
  • The sum of n does not exceed 106 .

Output

For each test cases, output an integer which denotes the maximum.

Sample Input

4 1 1-1 2 2 -14 2 1-1 2 2 -14 2 2-1 2 2 -14 2 10-1 2 2 -1

Sample Output

3420

 

 

//题意,最多选 m 次区间的和的绝对值 - c 的值,要求和最大,且所有点最多选一次作为端点

//贪心题,只要把前缀和排序,每次选最大的,最小的,直到选出值为负数,或等于m次,即停止

1 #include 
2 #include
3 #include
4 #include
5 using namespace std; 6 #define MX 100005 7 #define LL long long 8 9 int n,m,c;10 int num[MX];11 LL sum[MX];12 13 int main()14 {15 while(~scanf("%d%d%d",&n,&m,&c))16 {17 sum[0]=0;18 for (int i=1;i<=n;i++)19 {20 scanf("%d",&num[i]);21 sum[i]=sum[i-1]+num[i];22 }23 sort(sum,sum+1+n);24 int l = 0 ,r = n;25 LL ans = 0;26 27 while (l
c)28 {29 ans+=abs(sum[r]-sum[l])-c;30 l++,r--;31 }32 printf("%I64d\n",ans);33 }34 return 0;35 }
View Code

 

转载于:https://www.cnblogs.com/haoabcd2010/p/6861598.html

你可能感兴趣的文章
北京一行(七)——返程
查看>>
解决无线局域网的七大安全难题
查看>>
Spring 让 LOB 数据操作变得简单易行
查看>>
[转]走出软件作坊:三五个人十来条枪 如何成为开发正规军(二)
查看>>
Linux常用快捷键
查看>>
25Mybatis_查询缓存的基本知识
查看>>
职场的第一个五年规划
查看>>
AWS中,如果使用了ELB,出现outofservice
查看>>
[转]小程序实现原理解析
查看>>
js图片预览
查看>>
[原]RHEL6网络配置
查看>>
双核旗舰处理器:德仪Omap4430、高通MSM8260、猎户S5PV310、Tegra2横向优点缺点比较...
查看>>
HTML5 新标签
查看>>
Git使用初步
查看>>
SVN使用教程之——分支、合并
查看>>
Linux下的Cacti网络管理系统--安装常见问题(一)
查看>>
NYOJ-7 街区最短路径
查看>>
android真机调试
查看>>
图文例解C++类的多重继承与虚拟继承
查看>>
POST与GET的区别
查看>>