【BZOJ 3636】教义问答手册 (分治+整体二分+dp)
description
“漢中沃野如關中,四五百里煙蒙蒙。黃云連天夏麥熟,水稻漠漠吹秋風。”——摘自 黃裳《漢中行》
“泉嶺精神不朽,漢中諸球永生。”——摘自《泉嶺精神創立者語錄》
“把神犇烤一烤,味道會更好。”——摘自《xhr語錄》
“秀恩愛有利于身心健康!”——摘自《泉嶺精神集大成者語錄》
“樓上說的對!”——摘自《泉嶺精神信徒語錄合集》
“不會做積分,怎么找妹子!”——摘自《xhr語錄》
“切實保護耕地以放置更多的哨戒炮。”——摘自《泉嶺精神信徒語錄合集》
“就算兩個包子一起吃掉,也不能阻止我修筑梯田。”——摘自《泉嶺精神創立者語錄》
“我來自泉嶺,他來自漢中,我們半道而逢。”——摘自《泉嶺精神集大成者語錄》
【問題描述】
作為泉嶺精神的締造者、信奉者、捍衛者、傳承者,Pear決定印制一些教義問答手冊,以滿足泉嶺精神日益增多的信徒。Pear收集了一些有關的詩選、語錄,其中部分內容摘錄在了【題目背景】里。這些語錄是按出現的時間排好序的——Pear很喜歡這樣的作風,于是決定在按時間排好序的基礎上,選擇部分語錄,制作成若干本教義問答手冊。
一共有N條語錄。Pear決定從中選出某一段時間內的所有語錄,在此基礎上印制大小為L的若干本教義問答手冊。Pear對印制的手冊有如下要求:
1.每本手冊必須包含這個區間內連續的恰好L條語錄。
2.不同手冊包含的語錄不能相同。
3.每條語錄有一個“主題相關程度”,這個數可正可負。Pear希望所有手冊的語錄的“主題相關程度”之和盡可能大。
例如,對于區間[3,15]和L=3,一種選擇方法是:[4,6]+[9,11]+[12,14]。這三個區間長度都恰好為L,且互不重疊。
Pear并沒有決定選哪段時間的語錄,因此他有Q次詢問。每次詢問,給出兩個數[l,r]表示候選語錄的范圍是第l條到第r條。你能回答出每個詢問的最大“主題相關程度”之和么?
Input
第一行兩個正整數N,L,含義如上所述。注意對于所有詢問,L都是一樣的。
第二行N個整數,絕對值<=10000。第i個數表示第i條語錄的“主題相關程度”。
接下來Q行,每行兩個正整數l和r,表示詢問區間。
Output
輸出Q行,每行表示這組詢問的答案。注意,這個答案可以是0,如果區間負數過于多的話。
Sample Input
15 3
3 1 5 -2 3 -2 -2 2 2 2 0 3 2 -1 0
9
8 10
10 10
9 11
2 14
5 14
5 13
12 13
7 13
2 10
Sample Output
6
0
4
17
11
11
0
11
12
Hint
【數據范圍】
對于10%的數據,N=1000,Q=1000,L<=50
對于另外20%的數據,N=100000,Q=100000,L<=5
對于另外20%的數據,N=100000,Q=100000,L<=10
對于100%的數據,N=100000,Q=100000,L<=50
Source
2014年國家集訓隊十五人互測
solution
從最原始的O(n2)O(n^2)O(n2)暴力入手
設f[i][j]f[i][j]f[i][j]表示區間[i,j][i,j][i,j]的答案最大值,sum[i]sum[i]sum[i]表示前綴和
f[i][j]=max(f[i][j?1],f[i][j?L]+sum[j]?sum[j?L])f[i][j]=max(f[i][j-1],f[i][j-L]+sum[j]-sum[j-L])f[i][j]=max(f[i][j?1],f[i][j?L]+sum[j]?sum[j?L])
分治,分界線midmidmid將[l,r][l,r][l,r]分為左右兩個區間
- 長度為LLL的一段完全屬于左區間/右區間
- 跨越了midmidmid在左右區間都有的一段
第一種完全屬于某半邊區間的就直接分治遞歸處理
考慮第二種情況,對每一個l′l'l′預處理出在[l′,mid][l',mid][l′,mid]區間選了若干個長度為LLL的區間,且在末尾選了xxx個數的最大值,然后對每一個r′r'r′預處理出在[mid+1,r‘’][mid+1,r‘’][mid+1,r‘’]區間選了若干個長度為LLL的區間,并在開頭選了xxx個數的最大值
fl[i][j]fl[i][j]fl[i][j]:以jjj為左端點,左區間末尾選了iii個數的最大值
fr[i][j]fr[i][j]fr[i][j]:以jjj為右端點,右區間開頭選了iii個數的最大值
最后詢問可以整體二分一并處理
思路好懂,主要是代碼細節很ex人
code
#include <cstdio> #include <iostream> using namespace std; #define maxn 100005 int n, L, Q; int p[maxn], ql[maxn], qr[maxn], sum[maxn];//前綴和差分 int fl[55][maxn], fr[55][maxn]; int Left[maxn], Right[maxn], ans[maxn]; //fl[i][j]:以j為左端點 在末尾選了i個數 的最大值 //fr[i][j]:以j為右端點 在開頭選了i個數 的最大值 //預處理時的最大值只加了完整L的區間值 void calc_L( int l, int r ) {//對左區間進行預處理 for( int i = 0;i < min( r - l + 1, L );i ++ ) {//枚舉跨越mid的在區間末尾選的長度i fl[i][r - i + 1] = 0;for( int j = r - i;j >= l;j -- )//枚舉區間的左端點jfl[i][j] = j + L - 1 > r - i ? 0 : max( fl[i][j + 1], fl[i][j + L] + sum[j + L - 1] - sum[j - 1] );//r-i就是不與枚舉末尾長度i的起始點相交的第一個點//換言之[r-i+1,r]就是枚舉的一個跨越mid的L區間在左半邊的部分 //三目運算符判斷是否以j為左端點時可以劃分出一個完整的在區間的L且不交 (j~j+L-1)} } /* fl[L]:一個跨越mid的長度L區間在左半邊就有L個 也就相當于壓根沒跨越 fr[L]:同理也相當于壓根沒跨越 此情況恰好與fl[0],fr[0]差了一個L的區間劃分循環 故可以由fl[0],fr[0]表示 */ void calc_R( int l, int r ) {for( int i = 0;i < min( r - l + 1, L );i ++ ) {fr[i][l + i - 1] = 0;//[l,l+i-1]就是枚舉的一個跨越mid的L劃分區間在右半邊的部分 for( int j = l + i;j <= r;j ++ )fr[i][j] = j - L + 1 < l + i ? 0 : max( fr[i][j - 1], fr[i][j - L] + sum[j] - sum[j - L] );//三目運算符判斷是否以j為右端點時可以劃分出一個完整的在區間的L且不交 (j-L+1~j)} }void solve( int Ql, int Qr, int l, int r ) {if( Ql > Qr || r - l + 1 < L ) return;int mid = ( l + r ) >> 1;int lenl = 0, lenr = 0;calc_L( l, mid );calc_R( mid + 1, r );for( int i = Ql;i <= Qr;i ++ ) {int id = p[i];if( qr[id] <= mid ) Left[++ lenl] = id;else if( ql[id] > mid ) Right[++ lenr] = id;else {ans[id] = fl[0][ql[id]] + fr[0][qr[id]];//不存在跨越mid的L區間的情況下 最大值//dp動態規劃預處理已經做到局部最優解for( int j = max( 1, L - ( qr[id] - mid ) );j <= mid - ql[id] + 1 && j < L;j ++ )ans[id] = max( ans[id], ( mid - j < l ? 0 : fl[j][ql[id]] ) + ( mid + L - j + 1 > r ? 0 : fr[L - j][qr[id]] ) + sum[mid + L - j] - sum[mid - j] );/*mid-j mid+1+L-j都是兩邊不相交的第一個點ps:注意括號問題 要把三目運算符整個括在一起 不然會錯該跨越mid的區間應為 mid-j+1 ~ mid+1 + L-j - 1 枚舉跨越mid的L區間的左區間長度j=max(1,L-(qr[id]-mid))保證至少要有1個 且 該區間的右端點抵到整個詢問區間的右端點qr[id]mid-ql[id]+1&&j<L保證至多有L-1個這樣右邊才至少有一個 且 該區間的最多只能抵到整個詢問區間的左端點ql[id]判斷一下mid-j<l沒有因為只預處理了左端點>=l的其余部分應該全為0同理右邊判斷一下mid+L-j+1>r沒有只處理了右端點<=r其余部分應該全為0然后加上跨越的長度為L的區間的a值和但是好像去掉判斷也是AC的???不懂了 按道理不能去掉的啊???ans[id] = max( ans[id], fl[j][ql[id]] + fr[L - j][qr[id]] + sum[mid + L - j] - sum[mid - j + 1 - 1] );*/}}for( int i = 1;i <= lenl;i ++ ) p[Ql + i - 1] = Left[i];for( int i = 1;i <= lenr;i ++ ) p[Ql + lenl + i - 1] = Right[i];solve( Ql, Ql + lenl - 1, l, mid );solve( Ql + lenl, Ql + lenl + lenr - 1, mid + 1, r );//注意這里不再是solve(Ql+lenl,Qr,mid+1,r); 進行分類后有一些詢問操作是已經處理了的 }int main() {scanf( "%d %d", &n, &L );for( int i = 1;i <= n;i ++ ) {scanf( "%d", &sum[i] );sum[i] += sum[i - 1];}scanf( "%d", &Q );for( int i = 1;i <= Q;i ++ ) {p[i] = i;scanf( "%d %d", &ql[i], &qr[i] );}solve( 1, Q, 1, n );for( int i = 1;i <= Q;i ++ )printf( "%d\n", ans[i] );return 0; } //代碼參考博客:https://www.cnblogs.com/Orz-IE/p/12039213.html總結
以上是生活随笔為你收集整理的【BZOJ 3636】教义问答手册 (分治+整体二分+dp)的全部內容,希望文章能夠幫你解決所遇到的問題。
- 上一篇: 「LibreOJ NOI Round #
- 下一篇: 高考前一个月需要做什么 高考前一个月的备