首页 > 代码库 > codeforces332B - Maximum Absurdity 线段数 or dp
codeforces332B - Maximum Absurdity 线段数 or dp
题意：给你一个序列，找两个长度为 k 且没有重合区间的数使得其和最大
解题思路：
1）线段树
想了半天想不出只能先用线段树撸了一发，这题dp 第一名只要了 9分钟。
就是把起点为 i 长度为 k 的和预处理出来，再用线段树枚举去找。
解题代码：
1 // File Name: 332b.cpp 2 // Author: darkdream 3 // Created Time: 2014年07月30日 星期三 08时10分45秒 4 5 #include<vector> 6 #include<list> 7 #include<map> 8 #include<set> 9 #include<deque> 10 #include<stack> 11 #include<bitset> 12 #include<algorithm> 13 #include<functional> 14 #include<numeric> 15 #include<utility> 16 #include<sstream> 17 #include<iostream> 18 #include<iomanip> 19 #include<cstdio> 20 #include<cmath> 21 #include<cstdlib> 22 #include<cstring> 23 #include<ctime> 24 #define LL long long 25 using namespace std; 26 #define M 200004 27 struct node{ 28 int l , r ,m; 29 LL maxn,s; 30 }tree[M <<2]; 31 LL a[200004]; 32 LL sum[200004]; 33 int L(int x) 34 { 35 return 2 * x; 36 } 37 int R(int x) 38 { 39 return 2 * x + 1; 40 } 41 void pushup(int c) 42 { 43 if(tree[L(c)].maxn >=tree[R(c)].maxn) 44 { 45 tree[c].maxn = tree[L(c)].maxn; 46 tree[c].s = tree[L(c)].s; 47 }else{ 48 tree[c].maxn = tree[R(c)].maxn; 49 tree[c].s = tree[R(c)].s; 50 } 51 } 52 void build(int c ,int l, int r) 53 { 54 tree[c].l = l ; 55 tree[c].r = r ; 56 tree[c].m = (l+r)/2; 57 if(l == r) 58 { 59 tree[c].maxn = sum[l]; 60 tree[c].s = l ; 61 return ; 62 } 63 build(L(c),l,tree[c].m); 64 build(R(c),tree[c].m+1,r); 65 pushup(c); 66 } 67 LL maxa; 68 int site; 69 void find(int c, int l , int r) 70 { 71 //printf("%d %d %d %d %d\n",c,tree[c].l,tree[c].r,l,r); 72 if(r < l ) 73 return ; 74 if(l <= tree[c].l && r >= tree[c].r) 75 { 76 if(tree[c].maxn > maxa) 77 { 78 maxa = tree[c].maxn; 79 site = tree[c].s; 80 } 81 return ; 82 } 83 if(l <= tree[c].m) 84 find(L(c),l,r); 85 if(r > tree[c].m) 86 find(R(c),l,r); 87 } 88 int main(){ 89 int n , k; 90 scanf("%d %d",&n,&k); 91 int temp ; 92 a[0] = 0 ; 93 for(int i = 1; i <= n;i ++) 94 { 95 scanf("%d",&temp); 96 a[i] = a[i-1] + temp; 97 } 98 for(int i = 1 ;i <= n-k+1; i ++) 99 {100 sum[i] = a[i+k-1] - a[i-1];101 }102 build(1,1,n-k+1);103 LL ans = -1e9;104 int a, b ; 105 for(int i =1 ;i <= n-k+1;i ++)106 {107 maxa = -1e9 ;108 site = 0 ; 109 find(1,i+k,n-k+1);110 if(sum[i] + maxa > ans)111 {112 ans = sum[i] + maxa;113 a= i ; 114 b = site;115 }116 }117 printf("%d %d\n",a,b);118 return 0;119 }
2）由第一种思路突然想到还可以预处理出来 i 以后 的最大值是多少，位置是多少，这样就可以直接dp了
1 // File Name: 332b.1.cpp 2 // Author: darkdream 3 // Created Time: 2014年07月30日 星期三 10时13分41秒 4 5 #include<vector> 6 #include<list> 7 #include<map> 8 #include<set> 9 #include<deque>10 #include<stack>11 #include<bitset>12 #include<algorithm>13 #include<functional>14 #include<numeric>15 #include<utility>16 #include<sstream>17 #include<iostream>18 #include<iomanip>19 #include<cstdio>20 #include<cmath>21 #include<cstdlib>22 #include<cstring>23 #include<ctime>24 #define LL long long 25 #define maxn 200050 26 using namespace std;27 LL a[maxn];28 LL sum[maxn];29 LL m[maxn];30 int s[maxn];31 int n , k ; 32 int main(){33 scanf("%d %d",&n,&k);34 a[0] = 0 ; 35 int temp ; 36 for(int i = 1;i <= n;i ++)37 {38 scanf("%d",&temp);39 a[i] =a[i-1]+ temp; 40 }41 int p = n - k + 1; 42 for(int i = 1;i <= p ; i ++)43 {44 sum[i] = a[i+k-1] - a[i-1];45 }46 m[p] = sum[p];47 s[p] = p ; 48 49 for(int i = p -1;i >= 1 ;i --)50 {51 if(sum[i] >= m[i+1])52 {53 m[i] = sum[i];54 s[i] = i ;55 }else{56 m[i] = m[i+1];57 s[i] = s[i+1];58 }59 }60 int a, b ;61 LL maxa = -1e9 ; 62 for(int i =1 ;i <= p;i ++)63 {64 if(sum[i] + m[i+k] > maxa) 65 {66 a = i ; 67 b = s[i+k];68 maxa = sum[i] + m[i+k];69 }70 }71 printf("%d %d\n",a,b);72 return 0;73 }
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。