hdu5586

发表于 | 分类于 ， | 阅读数 次

链接:hdu5586

Problem Description

  • There is a number sequence {A}_{1},{A}_{2}….{A}_{n},you can select a interval [l,r] or not,all the numbers
  • {A}_{i}(l \leq i \leq r) will become f({A}_{i}).f(x)=(1890x+143) mod 10007.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\leq n\leq {10}^{5})
  • Next line contains n integers {A}_{1},{A}_{2}….{A}_{n}.(0\leq {A}_{i}\leq {10}^{4})
  • It’s guaranteed that \sum n\leq {10}^{6}.

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

题解

  • 最大子段和
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cmath>
#include<cstring>
#include<algorithm>
#define rep(i,x,y) for(register int i=x;i<=y;++i)
#define repd(i,x,y) for(register int i=x;i>=y;--i)
#define ll long long
using namespace std;
const int N=1e7;
const int mod=10007;
ll a[N],b[N],c[N],ans;
int n,m;

int f(ll x){
    return (x%mod*1890+143)%mod;
}

int main(){
    while(~scanf("%d",&n)){
        ans=0;
        rep(i,1,n){
            scanf("%lld",&a[i]);
            b[i]=f(a[i])-a[i];
            ans+=a[i];
        }
        int tp=0,k=0;
        rep(i,1,n){
            if(tp+b[i]>0)tp+=b[i];
            else tp=0;
            if(tp>k)k=tp;
        }
        printf("%lld\n",ans+k);
    }
    return 0;
}