《藍貓炸彈》解題報告
1、題目描述
這天，藍貓2號來到了乙個實驗室，他正在對一排炸彈進行研究，這些炸彈排在一條直線上。為了方便，藍貓2號就把它們的位置用乙個數來表示，這個數就是這乙個炸彈與最左邊炸彈的距離，每乙個炸彈i都有乙個「威力值」si。如果藍貓2號直接引爆了乙個炸彈i，那麼它的威力就會向直線的兩邊擴散。
最開始時，這個威力的強度為si，每移動乙個單位的距離，威力強度就減1，如果到了某一處，威力強度為0了，這個威力就消失了。如果在威力沒有消失的時候，又遇到了其它的炸彈，那麼這乙個炸彈也會引爆。並且威力強度增加了，增加的值就是剛剛引爆的炸彈的「威力值」，並且這個威力強度也繼續沿著原來相同的方向擴散。
現在，藍貓2號想要直接的引爆最多k個炸彈，使得所有引爆的炸彈數最多，當然，已經爆了的炸彈就消失了，再也不會爆了。它必須等上一次**完全停止後才能進行下一次**，所以，藍貓2號找到了你，要你為他解決這個問題。
[輸入]
輸入檔案的第一行有兩個正整數n，k(1<=n<=10000，1<=k<=100），分別表示炸彈的個數和最多能直接引爆的炸彈數。
第二行有n個數p1,p2……pn，表示這n個炸彈的位置，用它與第乙個炸彈的距離來表示，第乙個炸彈在最左邊，並且有0=p1第三行有n個數s1,s2,s3……sn,從左到右表示這n個炸彈的威力值，1<=si<=109。
[輸出]
僅有乙個數，表示最多能引爆的炸彈數(包括直接引爆的和間接引爆的)。
[輸入樣例]
6 20 2 5 6 11 13
1 1 4 2 2 2
[輸出樣例]
5注：首先引爆第4個炸彈，這時第1、2、3、4個炸彈都爆了；然後再引爆第5個或者第6個炸彈，總共就引爆了5個炸彈，這已經是最多的了。
2、演算法分析
這道題的目標就是確定乙個炸彈序列，引爆最多的炸彈。在這個中間，求出炸彈的引爆範圍就是不可避免的了。但是遺憾的是，當乙個炸彈**後，有些炸彈就不能炸了，還有些炸彈雖然能炸，但是引爆的範圍會改變了！
總之，有太多的東西隨時間改變。
首先不急於去猜測演算法，而是考慮在最開始的時候，引爆乙個炸彈後**的範圍，把這個叫做「引爆範圍」，來分析引爆範圍的性質。
炸彈i的引爆範圍用[li,ri]表示，它表示直接引爆i後，li到ri的炸彈都爆了，顯然有1≤li≤i≤ri≤n。令，不難得出li=max，ri=min。來看下面的結論：
1 如果i2 如果炸彈i的引爆範圍包含炸彈j，而炸彈j的引爆範圍不包含炸彈i，那麼炸彈i的引爆範圍將包含炸彈j的引爆範圍。
結論①的證明：從直觀上來講，當j**到i時而引爆了i，威力強度大於si，而直接引爆i時，威力強度只有si，所以前者向左傳播的範圍更遠。根據定義來證明有：
sj-si>pj-pi所以對於kpi-pk，有(si-sk)+(sj-si)>(pi-pk)+(pj-pi)，即sj-sk>pj-pk。
由結論①可知，對於r的情況也會得出相似的性質。
結論②都可以根據①得出來。為了方便，如果炸彈i的引爆範圍包含炸彈j，那麼就記為e(i,j)。
看到了上面的兩個結論後，再來分析一系列直接引爆的炸彈的有什麼性質。如果有兩個炸彈i,j滿足e(i,j)，它們都是直接引爆的，那麼可以把這次**序列進行改變。
在所有的直接引爆的炸彈中，找到這樣的i,j滿足e(i,j)，並且i,j兩者在**序列中較早的應該盡量的晚，在這個前提下，保證較晚的盡量的早(這樣思路就會清晰一些)，如果i在j之前直接引爆（這時假設~e(j,i)，~表示非，這種情況後面包括了），那麼在i引爆之前，必然有若干位於i與j之間的炸彈引爆了才使得直接引爆i時j不會被引爆。而在i後直接引爆的炸彈裡，任意兩個x,y都不滿足e(x,y)，不難證明它們與**順序無關了。可以這樣改變序列，把在i之前引爆而位於i與j之間的炸彈從引爆序列中刪掉。
這時，到了直接引爆i後，j會引爆，這時**的範圍顯然比直接引爆j的範圍大了。這是不是有利的？是的，雖然這會引爆後面需要直接引爆的炸彈，但是，由結論①②可知，只要引爆了這樣的炸彈，它的效果就會比直接引爆那個炸彈要好，所以這是有利的。
如果j在i的前面，則可以考慮在原來需要引爆j的時候直接的引爆i，這樣效果也不比原來的差。
所以上面得到的結論就是：
③：不會有兩個直接引爆的炸彈i，j滿足e(i,j)。
這樣，問題變成了要求一些區間，使得區間的並最大，並且任意兩個直接引爆的炸彈i,j不滿足e(i,j)，答案就只會與直接引爆的炸彈有關，而與它們的**順序無關，這樣問題就簡化了不少。
現在來設計演算法，首先必須要求出l，r。由於求的方法類似，只討論求l，由於li=max
這樣，在x1中的元素可以直接計算出方程中的最大值。在x3的元素對方程沒有影響。雖然在x2中的元素有一些對方程有影響，有一些沒有，但是它們有乙個很明顯的區別，那就是：
rx與j的大小關係。由於j是定值，所以在x2中的x，只要有lj≤rxf[i,j]=max，由於rj可以移出來，所以對於x2中的元素x，建樹的關鍵字是f[i-1,x]-rx，對於每乙個元素x，樹中x對應的葉子節點儲存的就是：max。
這樣，最開始不僅要記錄按l值從小到大排序的表，也要計算乙個按照r值從小到大排好序的表。
再來總結一下整個演算法，首先用o(n)的時間複雜度計算出每乙個炸彈的l，r值，然後從f[i-1]到f[i]的轉移中，維護一棵樹並記下乙個最大值max1（不需要記x1，只需要記乙個最大的f[i-1,x]就可以了）。按照j的l值從小到大計算f[i,j]，計算過程中，把滿足rxrx了，這個x不需要在x2中計算也不會在x2中計算了，整個演算法的複雜度是o(knlog2n)。
這個複雜度能夠承受了，最大的點(n=10000,k=100)也只需要0.95s(pentium 4 1.70ghz free pascal v1.0.6)。
解決問題的思路是：首先需要分析性質從乙個非多項式演算法得到乙個多項式演算法，然後需要利用性質從乙個多項式演算法得到乙個更優的多項式演算法。但是，問題是否就此解決了呢？
演算法有沒有進一步優化呢？能不能從o(knlog2n)降到o(kn)呢？有興趣的可以繼續思考。
[參考文獻]
《演算法藝術與資訊學競賽劉汝佳黃亮著
[討論]
在與肖天的討論中否決了o(kn)的演算法，只好用o(knlog2n)的了。
[感謝]
肖天、金愷
3、程式
const
inputfile= '';
outputfile='';
《花生採摘》解題報告
by sx349 摘要 核心演算法思想 貪心 主要資料結構 其他輔助知識 時間複雜度 空間複雜度 題目大意 給定乙個非空矩陣，每次都從中選擇乙個最大值並將其從矩陣中排除，將這些取出的數排序後計算其花費 相鄰兩數的花費是其在矩陣之間的曼哈頓距離 求在給定最大花費下，能取到的最大值的最大總和。演算法分析...
選擇解題技巧2Copy
2011年4月高考數學複習專題選擇題 填空題解題技巧 二 1.設a b 1，則logab,logba,logabb的大小關係是 2.如果函式f x x2 bx c對任意實數t都有f 2 t f 2 t 那麼f 1 f 2 f 4 的大小關係是 3.cos2 cos2 120 cos2 240 的值為...
古詩詞鑑賞分類解題指導2
古詩詞鑑賞要求考生調動知識積累 生活閱歷和審美情趣去感知詩歌形象，品味詩歌語言和表達技巧，領略詩歌情感，並用語言 準確 簡潔 完整 通順 地加以表達。1.形象 形象一般是指詩中的抒情主人公，也包括詩人著意刻畫或者是與詩人有密切關係的人物形象，比如 琵琶行 中的琵琶女，是詩人塑造的主人公形象，而詩人自...