hdu 5586 sum

时间:2022-09-09 11:29:19

Problem Description

There is a number sequence A1,A2....An,you can select a interval [l,r] or not,all the numbers Ai(l≤i≤r) will become f(Ai).f(x)=(1890x+143)mod10007.After that,the sum of n numbers should be as much as possible.What is the maximum sum?





Input

There are multiple test cases.

First line of each case contains a single integer n.(1≤n≤105)

Next line contains n integers A1,A2....An.(0≤Ai≤104)

It's guaranteed that ∑n≤106.





Output

For each test case,output the answer in a line.





Sample Input

2

10000 9999

5

1 9999 1 9999 1





Sample Output

19999

22033

动态规划!!!!!

代码:

#include<iostream>
#include <string>
#include <algorithm>
using namespace std;
long long a[100005],b[100005],sum;
int main()
{
int n,m,i,j,k;
while(cin>>n)
{ sum=0;
for(i=1;i<=n;i++)
{cin>>a[i];
b[i]=(1890*a[i]+143)%10007-a[i];
sum+=a[i];
}
b[0]=0;
for(i=1;i<=n;i++)
b[i]=max(b[i],b[i-1]+b[i]);
sort(b,b+n+1);
cout<<sum+b[n]<<endl;
}
return 0;
}

hdu 5586 sum的更多相关文章

  1. hdu 5586 Sum【dp最大子段和】

    题目链接:http://acm.hdu.edu.cn/showproblem.php?pid=5586 Sum Time Limit: 2000/1000 MS (Java/Others)    Me ...

  2. hdu 5586 Sum 最大子段和

    Sum Time Limit: 20 Sec Memory Limit: 256 MB 题目连接 http://acm.hdu.edu.cn/showproblem.php?pid=5586 Desc ...

  3. hdu 5586 Sum(dp&plus;技巧)

    Problem Description There )mod10007.After that,the sum of n numbers should be as much as possible.Wh ...

  4. hdu 5586 Sum 基础dp

    Sum Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 65536/65536 K (Java/Others) Problem Desc ...

  5. HDU - 5586 Sum(区间增量最大)

    题意:将数组A的部分区间值按照函数f(Ai)=(1890*Ai+143)mod10007修改值,区间长度可以为0,问该操作后数组A的最大值. 分析:先求出每个元素的增量,进而求出增量和.通过b[r]- ...

  6. HDOJ&lpar;HDU&rpar;&period;1258 Sum It Up &lpar;DFS&rpar;

    HDOJ(HDU).1258 Sum It Up (DFS) [从零开始DFS(6)] 点我挑战题目 从零开始DFS HDOJ.1342 Lotto [从零开始DFS(0)] - DFS思想与框架/双 ...

  7. HDU 5586 &lpar;dp 思想&rpar;

    Sum Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 65536/65536 K (Java/Others) Total Submis ...

  8. hdu 1258 Sum It Up(dfs&plus;去重)

    题目大意: 给你一个总和(total)和一列(list)整数,共n个整数,要求用这些整数相加,使相加的结果等于total,找出所有不相同的拼凑方法. 例如,total = 4,n = 6,list = ...

  9. 数论 --- 费马小定理 &plus; 快速幂 HDU 4704 Sum

    Sum Problem's Link:   http://acm.hdu.edu.cn/showproblem.php?pid=4704 Mean: 给定一个大整数N,求1到N中每个数的因式分解个数的 ...

随机推荐

  1. C&num;创建安全的栈&lpar;Stack&rpar;存储结构

    在C#中,用于存储的结构较多,如:DataTable,DataSet,List,Dictionary,Stack等结构,各种结构采用的存储的方式存在差异,效率也必然各有优缺点.现在介绍一种后进先出的数 ...

  2. java servlet的工作原理

    servlet本质上就是java类嘛.不过是有特殊规范的java类而已.下面就说一说为什么servlet要有特殊规范. 首先,考虑一下什么地方用servlet,WEB应用,而且是需要servlet容器 ...

  3. SilverLight MD5加密

    效果体验:http://keleyi.com/tool/md5.htm 嵌入页面的代码: <div style="width:400px;height:230px"> ...

  4. 如何让Qt 的程序等待一段时间(等待的同时,还让主界面刷新图片)good

    后面这种方法可以不影响其他线程的响应,又可以达到等待的目的. 测试的一个小例子: class Widget : public QWidget { Q_OBJECT public: Widget(QWi ...

  5. ecshop去掉head文件中ECSHOP v2&period;7&period;3标记的方法

    去掉ecshop中<meta name="Generator" content="ECSHOP v2.7.3" />的方法:打开includes/c ...

  6. iOS基础 - 相片浏览器

    一.需求分析 点击照片从当前照片位置动画弹出新的视图控制器显示选中的照片,新的视图控制器为全屏显示,背景为黑色,再次点击照片动画缩小至当前选中的照片位置,双击放大照片,如果已经放大则缩小,在新的视图控 ...

  7. 代码编写规范说明书(c&num;&period;net与asp&period;net)

    代码编写规范说明书(c#.net与asp.net) 目 录1 目的2 范围3 注释规范3.1 概述3.2 自建代码文件注释3.3 模块(类)注释3.4 类属性注释3.5 方法注释3.6 代码间注释4 ...

  8. erlang并发编程(二)

    补充-------erlang并发编程 Pid =spawn(fun()-> do_sth() end). 进程监视: Ref = monitor(process, Pid)靠抛异常来终结进程 ...

  9. spingBoot整合mybatis&plus;generator&plus;pageHelper

    spingBoot整合mybatis+generator+pageHelper 环境/版本一览: 开发工具:Intellij IDEA 2018.1.4 springboot: 2.0.4.RELEA ...

  10. JMeter学习(二十四)HTTP属性管理器HTTP Cookie Manager、HTTP Request Defaults(转载)

    转载自 http://www.cnblogs.com/yangxia-test Test Plan的配置元件中有一些和HTTP属性相关的元件:HTTP Cache Manager.HTTP Autho ...