hdu-5568SUM (dp)

 1 #include<stdio.h>
 2 #include<algorithm>
 3 #include<iostream>
 4 #include<stdlib.h>
 5 #include<vector>
 6 #include<queue>
 7 #include<cstdio>
 8 #include<string.h>
 9 typedef long long ll;
10 using namespace std;
11 ll a[100005];
12 ll b[100005];
13 
14 int main(void)
15 {
16     ll n,i,j,k,p,q;
17 
18     while(scanf("%lld",&n)!=EOF)
19     { ll tt=0;
20         for(i=0; i<n; i++)
21         {
22             scanf("%lld",&a[i]);
23             tt+=a[i];
24         }
25         for(i=0; i<n; i++)
26         {
27             b[i]=(1890*a[i]+143)%10007-a[i];
28         }
29         ll sum=0;
30         ll cnt=b[0];
31         if(sum<cnt)
32         {
33             sum=cnt;
34         }
35         for(i=1; i<n; i++)
36         {
37             if(b[i-1]>=0)
38             {
39                 b[i]+=b[i-1];
40 
41             }
42             if(sum<b[i])
43             {
44                 sum=b[i];
45             }
46         }
47         if(sum<0)
48         {
49             sum=0;
50         }
51         printf("%d\n",sum+tt);
52     }
53     return 0;
54 
55 
56 }