加入收藏 | 设为首页 | 会员中心 | 我要投稿 李大同 (https://www.lidatong.com.cn/)- 科技、建站、经验、云计算、5G、大数据,站长网!
当前位置: 首页 > 大数据 > 正文

CF#67 75d Big Maximum Sum

发布时间:2020-12-14 04:17:33 所属栏目:大数据 来源:网络整理
导读:~~~题面~~~ 题解: 观察到拼接后的数据范围过大,无法O(n)解决,但是大区间是由很多小区间组成,而小区间是固定的,不会变化,所以可以考虑预处理出每个小区间的信息,然后根据给定序列按顺序一步一步合并区间信息。 跟线段树维护区间最大子段和类似,要合并

~~~题面~~~

题解:

  观察到拼接后的数据范围过大,无法O(n)解决,但是大区间是由很多小区间组成,而小区间是固定的,不会变化,所以可以考虑预处理出每个小区间的信息,然后根据给定序列按顺序一步一步合并区间信息。

  跟线段树维护区间最大子段和类似,要合并2个区间我们只需要知道如下信息:

  前缀最大子段和,后缀最大子段和,当前区间最大子段和。

  那么转移方式如下:

  1,对于区间最大子段和而言,要么是继承2个区间中的某个最大子段和,要么是用上一个区间的后缀最大子段和+后一个区间的前缀最大子段和凑成一个子段和作为新的最大子段和,所以3者取max即可。

  2,对于前缀最大值而言,,,其实我们在转移的时候并不需要用到上一个区间的前缀最大值,因此无需再次维护。

  3,对于后缀最大值而言,要么是继承后一个区间的后缀最大子段和,要么是上一个区间的后缀最大值+后一个区间的整个区间凑成的新后缀最大值,2者取max即可。

 1 #include<bits/stdc++.h>
 2 using namespace std;
 3 #define R register int
 4 #define AC 50
 5 #define ac 5000
 6 #define LL long long
 7 
 8 int n,m,len;
 9 LL l[AC],r[AC],mx[AC],sum[AC],ans,rr;
10 int s[ac];
11 
12 inline int read()
13 {
14     int x = 0;char c = getchar();bool z = false;
15     while(c > 9 || c < 0) 
16     {
17         if(c == -) z = true;
18         c = getchar();
19     }
20     while(c >= 0 && c <= 9) x = x * 10 + c - 0,c = getchar();
21     if(!z) return x;
22     else return -x;
23 }
24 
25 inline void upmax(LL &a,LL b)
26 {
27     if(b > a) a = b;
28 }
29 
30 void pre()
31 {
32     n = read(),m = read();
33     for(R i = 1; i <= n; i ++)
34     {
35         len = read();
36         for(R j = 1; j <= len; j ++) s[j] = read(),sum[i] += s[j];
37         LL tmp = 0;
38         for(R j = 1; j <= len; j ++) tmp += s[j],upmax(l[i],tmp);
39         tmp = 0;
40         for(R j = len; j; j --) tmp += s[j],upmax(r[i],tmp);
41         tmp = 0;
42         for(R j = 1; j <= len; j ++)
43         {
44             tmp += s[j];
45             upmax(mx[i],tmp);
46             if(tmp < 0) tmp = 0;
47         }
48     }
49 }
50 
51 void work()
52 {
53     int x;
54     x = read();
55     rr = r[x],ans = mx[x];
56     for(R i = 2; i <= m; i ++)
57     {
58         x = read();//读入右区间
59         upmax(ans,mx[x]);
60         upmax(ans,rr + l[x]);
61         rr = rr + sum[x];
62         upmax(rr,r[x]);
63     }
64     cout << ans << endl;
65 }
66 
67 int main()
68 {
69     //freopen("in.in","r",stdin);
70     pre();
71     work();
72     //fclose(stdin);
73     return 0;
74 }
View Code

(编辑:李大同)

【声明】本站内容均来自网络,其相关言论仅代表作者个人观点,不代表本站立场。若无意侵犯到您的权利,请及时与联系站长删除相关内容!

    推荐文章
      热点阅读