http://acm.hdu.edu.cn/showproblem.php?pid=1231
之前用并查集来做的；
现在用dp来做：
dp的状态方程：dp[i]=max(dp[i-1]+a[i],a[i]);
Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 65536/32768 K (Java/Others) Total Submission(s): 16818 Accepted Submission(s): 7386
|
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
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61 |
#include<iostream>#include<cstring>using
namespace std;int Max(int
x,int y){ if(x<y) return
y; else return
x;}int
main(){ int
k,i,ans,r[20000],s,q,e; int
a[20000],dp[20000]; for(;;) { q=0; memset(dp,0,sizeof(dp)); cin>>k; if(k==0) break; for(i=1;i<=k;i++) cin>>a[i]; for(i=1;i<=k;i++) { if(dp[i-1]+a[i]>a[i]) dp[i]=dp[i-1]+a[i]; else { dp[i]=a[i]; r[q++]=i; } } ans=-999999; for(i=1;i<=k;i++) { if(ans<dp[i]) { ans=dp[i]; s=i; } } for(i=q-1;i>=0;i--) { if(r[i]<=s) { e=r[i]; break; } } if(ans<0) { ans=0; cout<<ans<<" "<<a[1]<<" "<<a[k]<<endl; } else cout<<ans<<" "<<a[e]<<" "<<a[s]<<endl; } return
0;} |
原文：http://www.cnblogs.com/cancangood/p/3560125.html