首页 > itarticle > hdu5586 题解

hdu5586 题解

admin 11月 13, 2020 0

链接:hdu5586

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.(1leq nleq {10}^{5})

Next line contains n integers {A}_{1},{A}_{2}….{A}_{n}.(0leq {A}_{i}leq {10}^{4})

It’s guaranteed that sum nleq {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

题解

最大子段和


#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 (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("%lldn",ans+k);
    }
    return 0;
}