失落的圣誕節(jié)

Time Limit: 3000/1000MS (Java/Others) ??? Memory Limit: 65535/65535KB (Java/Others)

Submit? Status

在櫻滿集(Ouma Shuu, 簡稱集)成功阻止修一郎博士，救出楪祈(Yuzuriha Inori, 簡稱祈)之后，由于默示錄病毒的爆發(fā)，天王州環(huán)狀七號線內(nèi)被封鎖，

集所在的學(xué)校也在此之內(nèi)。封鎖很快變成了清掃，為了打敗政府的幽靈部隊(duì),逃出封鎖區(qū)域，集在學(xué)校建立了void王國。

每個(gè)學(xué)生都有自己專屬的void，每種專屬void都有對應(yīng)的屬性值，集能將各個(gè)學(xué)生專屬的void取出來，并交給他們使用。普通學(xué)生不能使用別人

的void，但是作為主角的集和祈能使用任意學(xué)生的void，顯然，如果集或者祈使用了某種void，那么該void的主人就不能再使用了。當(dāng)void在

集或者祈手中，void的屬性值會有所改變，并且集和祈能同時(shí)使用同一個(gè)學(xué)生的void，且使用相同void的時(shí)候，還會有額外加成的屬性值（這就

是傳說中愛的力量？）

為了打倒幽靈部隊(duì)，集決定派出 3 個(gè)人，他自己，祈和一個(gè)普通學(xué)生（精英戰(zhàn)術(shù)！）。現(xiàn)在希望你幫助集求出，他們 3 個(gè)人使用的void的屬性值的

和能達(dá)到的最大值。

Input

首先輸入一個(gè) t ，表示輸入數(shù)據(jù)組數(shù)，對于每組數(shù)據(jù)。

第一行為一個(gè)整數(shù) n ，表示擁有void的人數(shù)。（ 3≤n≤10000 ,所有屬性值小于 2000 ）

第二行為 n 個(gè)正整數(shù)，每個(gè)整數(shù)表示該種void的主人用它時(shí)的屬性值。

第三行為 n 個(gè)正整數(shù)，每個(gè)整數(shù)表示該種void被集使用時(shí)的屬性值。

第四行為 n 個(gè)正整數(shù)，每個(gè)整數(shù)表示該種void被祈使用時(shí)的屬性值。

第五行為 n 個(gè)正整數(shù)，每個(gè)整數(shù)表示該種void被集和祈同時(shí)使用時(shí)的屬性加成值。

Output

每組數(shù)據(jù)輸出一行。輸出滿足題目要求的最大屬性值。

Sample input and output

Sample Input Sample Output

1 4 200 300 400 200 150 200 450 400 100 300 700 500 100 100 100 100	1550

Hint

在正常情況下，同一種void不能被多個(gè)人使用，唯一的特例情況是題面中所說的集和祈同時(shí)使用的時(shí)候。

樣例解釋：

普通學(xué)生使用第二種void，屬性值為 300

集使用第三種void，屬性值為 450

祈使用第三種void，屬性值為 700

屬性加成為 100

My Solution

首先是有組合void的，分成2類? 1、maxN + maxSQ ；? 2、1）maxN2 + maxSQ ；2）maxN + maxSQ2
然后沒有組合void的，分成3類 1、maxN + ?這個(gè)時(shí)候?qū)?yīng)位置為mni? 然后在它的兩邊分別掃描S、Q 可以得 max4 2、maxN2 + 這個(gè)時(shí)候?qū)?yīng)位置為mni2? 然后在它的兩邊分別掃描S、Q 可以得 max5 3、maxN3 +?這個(gè)時(shí)候?qū)?yīng)位置為mni3? 然后在它的兩邊分別掃描S、Q 可以得 max6 ? ? ?//因?yàn)榭赡躈的第1大和第2大位置都被占了，且集和祈的效果更好
具體請看下面，雖然Length挺長的，但Time還是做過那個(gè)題目目前為止最快的，Memory也盡可能小了，別人懶得優(yōu)化這個(gè)題目吧
#include <cstdio> #include <algorithm> //#define LOCAL using namespace std; const int maxn=10000+8; int N[maxn],S[maxn],Q[maxn],Sha,sum[maxn];int main() {#ifdef LOCALfreopen("a.txt","r",stdin);#endif // LOCAKint T,n,maxN,mni,mni2,maxN3,mni3, maxSQ,mqsi, maxs, maxq;scanf("%d",&T);while(T--){maxN=0;maxSQ=0;scanf("%d",&n);for(int i=0;i<n;i++){scanf("%d",&N[i]);if(maxN<N[i]) {maxN=N[i];mni=i;} }for(int i=0;i<n;i++)scanf("%d",&S[i]);for(int i=0;i<n;i++)scanf("%d",&Q[i]);for(int i=0;i<n;i++){scanf("%d",&Sha);sum[i]=Sha+S[i]+Q[i];if(maxSQ<sum[i]) {maxSQ=sum[i];mqsi=i;} }int max1=0,max2=0,max3=0, maxSQ2=0,maxN2=0;if(mni!=mqsi) max3=maxSQ+maxN;else{for(int i=0;i<n;i++)if(i!=mqsi) maxSQ2=max(maxSQ2,sum[i]);max1=maxN+maxSQ2; //max0for(int i=0;i<n;i++)if(i!=mni) if(maxN2<N[i]) {maxN2=N[i];mni2=i;}max2=maxN2+maxSQ;max3=max(max1,max2);}int max4=0,max5=0,max6=0;maxs=0;maxq=0;for(int i=0;i<mni;i++){maxq=max(maxq,Q[i]);maxs=max(maxs,S[i]);}for(int i=mni+1;i<n;i++){maxq=max(maxq,Q[i]);maxs=max(maxs,S[i]);}max4=maxq+maxs+maxN;maxq=0;maxs=0;for(int i=0;i<mni2;i++){maxq=max(maxq,Q[i]);maxs=max(maxs,S[i]);}for(int i=mni2+1;i<n;i++){maxq=max(maxq,Q[i]);maxs=max(maxs,S[i]);}max5=maxq+maxs+maxN2;maxN3=0;for(int i=0;i<n;i++)if(i!=mni&&i!=mni2) if(maxN3<N[i]) {maxN3=N[i];mni3=i;}maxq=0;maxs=0;for(int i=0;i<mni3;i++){maxq=max(maxq,Q[i]);maxs=max(maxs,S[i]);}for(int i=mni3+1;i<n;i++){maxq=max(maxq,Q[i]);maxs=max(maxs,S[i]);}max6=maxq+maxs+maxN3;printf("%d",max(max3,max(max4,max(max5,max6))));if(T) printf("\n");}return 0; }
沒有用線段樹，這里有3個(gè)要掃描的數(shù)組，再用數(shù)組建樹，加上函數(shù)相對for(;;)的時(shí)間開銷，時(shí)間復(fù)雜度差不多了，可能還會慢一點(diǎn)。 并且用for可以輕松的S、Q一起掃， 所以在這里就直接搞了。
謝謝

總結(jié)

以上是生活随笔為你收集整理的UESTC 764 失落的圣诞节 直接or线段树orRMQ的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。