【正文】 ：1=n=200，合并n堆石子最少需要耗費的力氣不超過2*109。問最少需要耗費多少力氣？：第一行一個整數(shù)n，第二行n個整數(shù)，表示順序排列的每堆石子的重量?，F(xiàn)在需要把它們合并成一堆石子。二叉樹數(shù)求由n個結(jié)點構(gòu)成的不同的二叉樹數(shù).樣例輸入:3樣例輸出:5題19。多邊形的三角劃分 N個頂點的凸多邊形，各頂點權(quán)值已知，要求劃分成N2個三角形，使各三角形頂點權(quán)值乘積之和為最小10576如右圖當n=4，各頂點的權(quán)值分別為10,5,7,6時，所求最小值為10*5*6+5*6*7=510。輸出：,該行只有一個整數(shù),表示得到的最多單詞個數(shù)。再接下來有一個正整數(shù)s，表示字典中單詞個數(shù)。分為k個部分。要求輸出最大的個數(shù)。例如字符串this中可包含this和is,選用this之后就不能包含th)。要求將此字母串分成k份(1k=40),且每份中包含的單詞個數(shù)加起來總數(shù)最大(每份中包含的單詞可以部分重疊。NOIP2001年提高組第3題統(tǒng)計單詞個數(shù)() 問題描述 給出一個長度不超過200的由小寫英文字母組成的字母串(約定。第一行是你程序得到的最小值，第二行是最大值。 以下n行每行有個整數(shù),其絕對值不大于104,按順序給出圈中的數(shù)字,首尾相接。丁丁請你編寫程序幫他贏得這個游戲。例如,對于下面這圈數(shù)字（n=4，m=2）：當要求最小值時,((21) mod 10)((4+3) mod 10)=17=7,要求最大值時,為((2+4+3) mod 10)(1 mod 10)=99=81。游戲是這樣的,在你面前有一圈整數(shù)(一共n個),你要按順序?qū)⑵浞譃閙個部分,各部分內(nèi)的數(shù)字相加, 相加所得的m個結(jié)果對10取模后再相乘,最終得到一個數(shù)k。NOIP2003年普及組第2題數(shù)字游戲（) 【問題描述】24131 丁丁最近沉迷于一個數(shù)字游戲之中。輸出所求得的最大乘積（一個自然數(shù)）。同時，為了幫助選手能夠正確理解題意，主持人還舉了如下的一個例子：有一個數(shù)字串：312， 當N=3，K=1時會有以下兩種分法： 1) 3*12=36 2) 31*2=62 這時，符合題目要求的結(jié)果是：31*2=62 現(xiàn)在，請你幫助你的好朋友XZ設計一個程序，求得正確的答案。在華羅庚先生的家鄉(xiāng)江蘇金壇,組織了一場別開生面的數(shù)學智力競賽的活動,你的一個好朋友XZ也有幸得以參加。 【輸入樣例】55 7 1 2 10【輸出樣例】145 3 1 2 4 5題14?！据敵龈袷健康?行：一個整數(shù)，為最高加分（結(jié)果不會超過4,000,000,000）。要求輸出；（1）tree的最高加分（2）tree的前序遍歷 【輸入格式】 第1行：一個整數(shù)n(n＜30)為節(jié)點個數(shù)。不考慮它的空子樹。區(qū)域動規(guī)：題13. 2003年提高組第3題加分二叉樹【問題描述】 設一個n個節(jié)點的二叉樹tree的中序遍歷為(l,2,3,…,n),其中數(shù)字1,2,3,…,n為節(jié)點編號。【輸出格式】，該行只有一個整數(shù)，代表開采出所有礦藏最多能得到的錢數(shù)。【輸入格式】：第一行:一個整數(shù)n，代表有n個礦點。由于該稀有金屬的在地球上存量非常稀少，市場上價格越來越高，已知開采第一天的價格為1，第二天的價格為2，依次類推?！締栴}背景】A公司在南極大陸發(fā)現(xiàn)了一個稀有金屬礦，該礦沿直線分布，共有n個點，每個點有一定量的礦藏。，為他們兩人基因的最長公共部分的長度?？梢圆贿B續(xù)。且對于每個人，這n個數(shù)字互不相同。最長公共子序列：勇闖黃金十二宮……射手宮同濟ACM第1108題Problem “已知艾爾里斯和弟弟艾爾里亞的基因基本相同，由于基因表達起來不方便，所以就用n個數(shù)字來表示。表示可以開通輪渡的最大線路數(shù)。表示這一對友好城市與河源頭的距離(不過100000)，其中A代表北岸城市、B代表南岸城市。Input ：N（1≤N≤2004）。iRabbit因為備戰(zhàn)競賽，所以十分繁忙，沒有時間來編寫程序，所以交給手下的TCR和sceoy解決。iRabbit希望能在保證安全的情況下，盡可能多地開通航線。iRabbit決定禁止船只航線相交。為了城市關(guān)系的發(fā)展，每對城市之間都想要開通輪渡。渡河Problem iRabbit的國家被一條河流(河流是直的)分成南北兩岸，南北兩岸各有N個城市。 【輸入樣例】8186 186 150 200 160 130 197 220 【輸出樣例】4【數(shù)據(jù)規(guī)?！繉τ?0％的數(shù)據(jù)，保證有n=20；對于全部的數(shù)據(jù)，保證有n=100。第二行有n個整數(shù)，用空格分隔，第i個整數(shù)Ti(130=Ti=230)是第i位同學的身高(厘米)?！据斎敫袷健?。合唱隊形是指這樣的一種隊形：設K位同學從左到右依次編號為1，2…，K，他們的身高分別為T1，T2，…，TK， 則他們的身高滿足T1...TiTi+1…TK(1=i=K)?！据斎霕永? 389 207 155 300 299 170 158 65【輸出樣例】62題31。第一行只有一個正整數(shù),表示最多能攔截的導彈數(shù)。輸入導彈依次飛來的高度（雷達給出的高度數(shù)據(jù)是不大于30000的正整數(shù)）：1）計算這套系統(tǒng)最多能攔截多少導彈；2）如果要攔截所有導彈最少要配備多少套這種導彈攔截系統(tǒng)。某天，雷達捕捉到敵國的導彈來襲。1999提高組第1題攔截導彈【問題描述】某國為了防御敵國的導彈襲擊，發(fā)展出一種導彈攔截系統(tǒng)?！据敵觥?，該行只有一個整數(shù)，表示最多能獲得的寶石數(shù)。每一行的兩個整數(shù)a和b,可能表示山洞a至山洞b間的單向通道，也可能表示山洞b至山洞a間的單向通道。這n個數(shù)間互相以一個空格分隔。 第一行有兩個整數(shù)n和m，分別表示山洞數(shù)和通道數(shù)，兩數(shù)間以一個空格分隔。從外面只能進入一次，然后從一個山洞至另一個山洞，直至走出山洞。某些山洞間可能會有通道相連，山洞間的通道是單向的，編號較小的山洞可以通過通道走至編號較大的山洞，編號較大的山洞不可以通過通道走至編號較小的山洞。題29。輸入整數(shù)F，V和矩陣A，輸出最大美學值和每束花擺放在各個花瓶中的花瓶編號。為取得最佳美學效果，必須在保持花束順序的前提下，使花的擺放取得最大的美學值?！据斎敫袷健浚?≤n≤18）【輸出格式】，即可能輸出序列的總數(shù)目【輸入樣例】 【輸出樣例】3 5【思考】如果1≤n≤3000，如何做？題28。現(xiàn)在可以進行兩種操作，從操作數(shù)序列的頭端移到棧的頭端（對應數(shù)據(jù)結(jié)構(gòu)棧的push操作）2. 將一個數(shù)，從棧的頭端移到輸出序列的尾端（對應數(shù)據(jù)結(jié)構(gòu)棧的pop操作）使用這兩種操作,由一個操作數(shù)序列就可以得到一系列的輸出序列。寧寧在復習棧的基本概念時，想到了一個書上沒有講過的問題，而他自己無法給出答案，所以需要你的幫忙。棧有兩種最重要的操作，即pop（從棧頂彈出一個元素）和push（將一個元素進棧）?！据斎霕永? 【輸出樣例】8 672 3 132 6 63 5 74 4 145 2 21 5 6 46 3 157 2 140 0 0題27?！据斎敫袷健?表示N*N的方格圖),接下來的每行有三個整數(shù),前兩個表示位置,第三個數(shù)為該位置上所放的數(shù)。在走過的路上,他可以取走方格中的數(shù)(取走后的方格中將變?yōu)閿?shù)字0)。2000年提高組第4題方格取數(shù)000000000013006000000700000014000002100040000150000001400000000000000B點A點【問題描述】 設有N*N的方格圖(N=30,我們將其中的某些方格中填入正整數(shù),而其他的方格中則放入數(shù)字0。2)任務2：輸出一個數(shù),表示路徑數(shù)。 1)任務1：第2行有兩個數(shù),表示右上角坐標(n,m)2)任務2：第2行有兩個數(shù),表示右上角坐標(n,m)第3行有兩個數(shù),表示起點坐標(x1,y1)第4行有兩個數(shù),表示終點坐標(x2,y2)【輸出格式】。如圖3所示,給出馬的起點坐標為(1,8),終點坐標為(3,8),則有2條路徑。NO39。 任務1：當n,m輸入之后,找出一條從左下角到右上角的路徑。馬走的規(guī)則為：(1)馬走日字；(2)馬只能向右走。【輸入樣例】2,3【輸出樣例】8,10馬圖1 馬的4種走法題25。1997年普及組第1題統(tǒng)計正方形和長方形個數(shù)【問題描述】 設有一個n*m方格的棋盤(1≤m,n≤1000),求出該棋盤中包含多少個正方形、多少個長方形(不包括正方形)?！据斎敫袷健?該行中有4個以空格分隔的數(shù),表示B點的坐標和馬的坐標【輸出格式】,該行只有一個數(shù),表示求得的路徑條數(shù)。棋盤用坐標表示,A 點坐標為(0,0)、B 點坐標為(n,m)(n,m為不超過 20 的整數(shù)),同樣馬的位置坐標是需要給出的(約定點:C≠點A,同時點C≠點B)。例如P8P1YB(4,8)右圖C點上的馬可以控制9個點(圖中的P1,P2,…,P8和C)。卒行走規(guī)則:可以C3向下、或者向右?！据斎霕永?】13 3【輸出樣例1】6【輸入樣例2】29 52 28 4【輸出樣例2】2P5P45876432010A(0,0)題23?！据斎敫袷健?1代表任務一,2代表任務二。此時,從A(1,1)出發(fā)至B(9,5),只有兩條路徑：路徑一：(1,1)(2,1)(3,1)(4,1)(5,1)(6,1)(7,1)(8,1)(9,1)(9,2)(9,3)(9,4)(9,5)路徑二：(1,1)(1,2)(1,3)(1,4)(1,5)(2,5)(3,5)(4,5)(5,5)(6,5)(7,5)(8,5)(9,5)程序要求：任務一：給出N,M后,求出所有從(1,1)出發(fā)到達(N,M)的路徑的條數(shù)。如圖,從(1,1)點出發(fā),至(3,3)點,共有6條不同的路徑： (1,1)(2,1)(3,1)(3,2)(3,3)； (1,1)(2,1)(2,2)(3,2)(3,3)； (1,1)(2,1)(2,2)(2,3)(3,3)；(1,1)(1,2)(2,2)(3,2)(3,3)；(1,1)(1,2)(2,2)(2,3)(3,