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 } (编辑:李大同) 【声明】本站内容均来自网络,其相关言论仅代表作者个人观点,不代表本站立场。若无意侵犯到您的权利,请及时与联系站长删除相关内容! |