Sum
Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 65536/65536 K (Java/Others)Total Submission(s): 287 Accepted Submission(s): 177
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.
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
Source
题目大意：
给n个数A1,A2....An,你可以选择一个区间(也可以不选)，区间里每个数x变成f(x),其中f(x)=(1890x+143)mod10007。问最后n个数之和最大可能为多少。解题思路：
就是比较一下大小就行了，但是是减去arr[i]的值。。。
代码：
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <cmath>
#include <vector>
#include <queue>
#include <algorithm>
#include <set>
using namespace std;
#define MM(a) memset(a,0,sizeof(a))
typedef long long LL;
typedef unsigned long long ULL;
const int maxn = 1e5+5;
const int mod = 1e4+7;
const double eps = 1e-10;
const int INF = 0x3f3f3f3f;
LL gcd(LL a, LL b)
{
if(b == 0)
return a;
return gcd(b, a%b);
}
int arr[maxn], data[maxn];
int main()
{
int n;
while(~scanf("%d",&n))
{
LL sum = 0;
for(int i=0; i<n; i++)
{
scanf("%d",&arr[i]);
sum += arr[i];
data[i] = ((arr[i]*1890+143)%mod) - arr[i];
}
LL Max = 0, tmp = 0;
for(int i=0; i<n; i++)
{
tmp += data[i];
if(tmp > Max)
Max = tmp;
if(tmp < 0)
tmp = 0;
}
LL ret = sum+Max;
printf("%I64d\n",ret);
}
return 0;
}
