网站开发小程序开发公司,公司网站建设行为规定,网页制作开版费,启动培训网站建设的请示题意#xff1a;求一个环中最大区间和#xff0c;区间长度 n。 用单调队列优化Dp#xff0c;核心内容是dp[i] max(sum[j]) - sum[i-1]。 这题最后的输出有很多要求#xff0c;如果有多个解#xff0c;输出起始位置最小的#xff1b;如果还有多个解#xff0c;输出…题意求一个环中最大区间和区间长度 n。 用单调队列优化Dp核心内容是dp[i] max(sum[j]) - sum[i-1]。 这题最后的输出有很多要求如果有多个解输出起始位置最小的如果还有多个解输出长度最小的。其实完全不用考虑因为我遍历的时候就是按起始位置从小到大的如果一个解和最优解相同并不更新记录的就是起始最小的结果。另一个要求亦然。 1 #include stdio.h2 #include string.h3 const int N 100010;4 const int INF 1000000000;5 int a[N],sum[N1];6 int max[N],dp[N],v[N];7 int s,e;8 int main()9 {
10 int T,n,k,i,Max,x,y;
11 scanf(%d,T);
12 while(T--)
13 {
14 scanf(%d%d,n,k);
15 for(i 1; i n; i)
16 scanf(%d,a[i]),
17 sum[i] sum[i-1] a[i];
18 for(i 1; i k; i)
19 sum[ni] sum[n-1i] a[i];
20 memset(max,0,sizeof max);
21 s e 0;
22 for(i 1; i k; i)
23 {
24 while(s e sum[i] sum[max[e]])
25 e--;
26 max[e] i;
27 }
28 for(i 1; i n; i)
29 {
30 while(s e max[s] i) s;
31 dp[i] sum[max[s]] - sum[i-1];
32 v[i] max[s];
33 while(s e sum[ik] sum[max[e]])
34 e--;
35 max[e] ik;
36 }
37 Max -INF;
38 for(i 1; i n; i)
39 if(dp[i] Max)
40 Max dp[i],
41 x i, y v[i];
42 printf(%d %d %d\n,Max,x, yn ?y%n :y);
43 }
44 return 0;
45 } 转载于:https://www.cnblogs.com/lzxskjo/archive/2012/08/29/2661184.html
