a164. 區間最大連續和
內容
:
給定一個整數序列Ai, 其中1<=i<=N。
有Q筆詢問,每次詢問一個正整數數對L, R,問閉區間 [AL, AR]的最大連續和。
什麼叫最大連續和呢?請參見d784: 連續元素的和
也就是說要找到兩個正整數i, j滿足L <=i <=j <= R,且極大化Ai + Ai+1 + ... + Aj的值。
當i, j有多組解時輸出i最小的、再有多組解輸出j最小的。
輸入說明
:
輸出說明
:
每組測資的輸出第一行請輸出"Case x:"表示為第x組測資,從1開始編號。
接下來輸出Q行,每行輸出三個數字依序表示該筆詢問的i, j以及Ai + Ai+1 + ... + Aj的值。
範例輸入
:
10 3
0 0 0 1 0 0 0 -8 -3 5
1 7
8 9
8 10
範例輸出
:
Case 1:
1 4 1
9 9 -3
10 10 5
提示
:
背景知識:
經典應用
第一個檔案就是範例。
第二個檔案共有十組,N=Q=100。
第三個檔案共有兩組,皆為極限測資。
出處
:
Asia - Nanjing - 2007/2008
(管理:
poao899)
作法 : 線段樹
參考 :
http://www.cppblog.com/MatoNo1/archive/2011/04/24/144901.html線段樹的區間是[i,j],節點編號k,左右子樹lc, rc,我們將儲存
1. 由左至右 : 從i 開始,但小於 j 的 最大連續和 (lmax)
2. 由右至左 : 從j 開始,但大於 i 的 最大連續和 (rmax)
3. 中間 : 此區間存在的最大連續和 (midmax)
4. 區間總和 (sum)
得到1. k.lmax = max(lc.lmax, lc.sum + rc.lmax);2. k.rmax = max(rc.rmax, rc.sum + lc.rmax);
3. k.midmax = max(lc.midmax, rc.midmax, lc.rmax + rc.lmax);4. k.sum = lc.sum + rc.sum;接下來,當我們調查[i,j] 時,會拆成很多個不相交的區間
[i, i1] [i2, i3] [i4..] ...
目前不連續到下一個區間的最大連續和 f0 =
max(k.midmax, f1 + k.lmax);/*區間中斷 or 連續+斷*/
目前可連續到下一個區間的最大連續和 f1 =
max(k.rmax, f1 + k.sum);/*新的連續 or 連續+連續*/
這個時候,就以我們平常所做的最大連續和"類似"了 (不代表相同)
這裡只是約略講一下,詳情請看參考網址
為了輸出最大連續和的 "最小"區間,搞得我人仰馬翻啦

雖然幾乎是照著打了,我仍學到很多,感謝分享的神犇
/**********************************************************************************//* Problem: a164 "區間最大連續和" from Asia - Nanjing - 2007/2008 *//* Language: C *//* Result: AC (272ms, 13790KB) on ZeroJudge *//* Author: morris1028 at 2011-06-28 12:40:03 *//**********************************************************************************/#include<stdio.h>#define N 262144#define Maxv 2147483647long long A[N], Ans, f0, f1;int B[N], st, ed, st0, ed0, st1, ed1;struct segment { int l, r, m; int lc, rc; int lst, led, rst, red, mst, med; long long sum, lmax, rmax, midmax;}ST[2*N + 2];int max(int x, int y) { return x >= y ? x : y;}void init(int l, int r, int k) { ST[k].l = l, ST[k].r = r, ST[k].m = (l + r)>>1; if(l == r) { ST[k].sum = ST[k].lmax = ST[k].rmax = ST[k].midmax = A[l]; ST[k].lst = ST[k].led = ST[k].rst = ST[k].red = ST[k].mst = ST[k].med = l; return ; } ST[k].lc = k<<1, ST[k].rc = (k<<1)+1; init(l, ST[k].m, ST[k].lc), init(ST[k].m+1, r, ST[k].rc); ST[k].sum = ST[ST[k].lc].sum + ST[ST[k].rc].sum; ST[k].lmax = max(ST[ST[k].lc].lmax, ST[ST[k].lc].sum + ST[ST[k].rc].lmax); ST[k].lst = Maxv, ST[k].led = Maxv;; if(ST[ST[k].lc].lmax == ST[k].lmax) ST[k].lst = ST[ST[k].lc].lst, ST[k].led = ST[ST[k].lc].led; if(ST[ST[k].lc].sum + ST[ST[k].rc].lmax == ST[k].lmax && (ST[k].lst > ST[ST[k].lc].l || (ST[k].lst == ST[ST[k].lc].l && ST[k].led > ST[ST[k].rc].led))) ST[k].lst = ST[ST[k].lc].l, ST[k].led = ST[ST[k].rc].led; ST[k].rmax = max(ST[ST[k].rc].rmax, ST[ST[k].rc].sum + ST[ST[k].lc].rmax); ST[k].rst = Maxv, ST[k].red = Maxv; if(ST[ST[k].rc].rmax == ST[k].rmax) ST[k].rst = ST[ST[k].rc].rst, ST[k].red = ST[ST[k].rc].red; if(ST[ST[k].rc].sum + ST[ST[k].lc].rmax == ST[k].rmax && (ST[k].rst > ST[ST[k].lc].rst || (ST[k].rst == ST[ST[k].lc].rst && ST[k].red > ST[ST[k].rc].r))) ST[k].rst = ST[ST[k].lc].rst, ST[k].red = ST[ST[k].rc].r; ST[k].midmax = max(max(ST[ST[k].lc].midmax, ST[ST[k].rc].midmax), ST[ST[k].lc].rmax + ST[ST[k].rc].lmax); ST[k].mst = Maxv, ST[k].med = Maxv; if(ST[ST[k].lc].midmax == ST[k].midmax) ST[k].mst = ST[ST[k].lc].mst, ST[k].med = ST[ST[k].lc].med; if(ST[ST[k].rc].midmax == ST[k].midmax && (ST[k].mst > ST[ST[k].rc].mst || (ST[k].mst == ST[ST[k].rc].mst && ST[k].med > ST[ST[k].rc].med))) ST[k].mst = ST[ST[k].rc].mst, ST[k].med = ST[ST[k].rc].med; if(ST[ST[k].lc].rmax + ST[ST[k].rc].lmax == ST[k].midmax && (ST[k].mst > ST[ST[k].lc].rst || (ST[k].mst == ST[ST[k].lc].rst && ST[k].med > ST[ST[k].rc].led))) ST[k].mst = ST[ST[k].lc].rst, ST[k].med = ST[ST[k].rc].led; }void query(int l, int r, int k) { if(ST[k].l > r || ST[k].r < l) return ; if(ST[k].l >= l && ST[k].r <= r) { f0 = max(ST[k].midmax, f1 + ST[k].lmax); if(ST[k].midmax == f0 && f1 + ST[k].lmax != f0) st0 = ST[k].mst, ed0 = ST[k].med; else if(f1 + ST[k].lmax == f0 && ST[k].midmax != f0) st0 = st1, ed0 = ST[k].led; else { if(ST[k].mst < st1 || (ST[k].mst == st1 && ST[k].med < ST[k].led)) st0 = ST[k].mst, ed0 = ST[k].med; else st0 = st1, ed0 = ST[k].led; } int pref1 = f1; f1 = max(ST[k].rmax, f1 + ST[k].sum); if(ST[k].rmax == f1 && pref1 + ST[k].sum != f1) st1 = ST[k].rst, ed1 = ST[k].red; else if(pref1 + ST[k].sum == f1 && ST[k].rmax != f1) st1 = st1, ed1 = ST[k].r; else { if(ST[k].rst < st1 || (ST[k].rst == st1 && ST[k].red < ST[k].r)) st1 = ST[k].rst, ed1 = ST[k].red; else st1 = st1, ed1 = ST[k].r; } if(f0 > Ans || (f0 == Ans && st > st0 || (st == st0 && ed > ed0))) Ans = f0, st = st0, ed = ed0; if(f1 > Ans || (f1 == Ans && st > st1 || (st == st1 && ed > ed1))) Ans = f1, st = st1, ed = ed1; return ; } query(l, r, ST[k].lc), query(l, r, ST[k].rc);}int Input() { char cha; unsigned int x = 0; while(cha = getchar()) if(cha != ' ' && cha != '\n' || cha == EOF) break; if(cha == EOF) return -1; x = cha-48; while(cha = getchar()) { if(cha == ' ' || cha == '\n') break; x = x*10 + cha-48; } return x; }main() { int n, Q, a, C = 0; int i, j; while(scanf("%d %d", &n, &Q) == 2) { for(a = 1; a <= n; a++) scanf("%lld", &A[a]); init(1, n, 1); printf("Case %d:\n", ++C); while(Q--) { i = Input(), j = Input(); f0 = f1 = 0, Ans = -2147483647, st0 = st1 = ed0 = ed1 = i; query(i, j, 1); printf("%d %d %lld\n", st, ed, Ans); } } return 0;}
文章定位: