最佳答案

1． 最長公共子序列 一個給定序列的子序列是在該序列中刪去若干元素后得到的序列。確切地說，若給定序列X=，則另一序列Z=是X的子序列是指存在一個嚴格遞增的下標序列 ，使得對于所有j=1,2,…,k有 2． 計算矩陣連乘積 在科學計算中經常要計算矩陣的乘積。矩陣A和B可乘的條件是矩陣A的列數等于矩陣B的行數。若A是一個p×q的矩陣，B是一個q×r的矩陣，則其乘積C=AB是一個p×r的矩陣。由該公式知計算C=AB總共需要pqr次的數乘。其標準計算公式為： 3． 凸多邊形的最優三角剖分 多邊形是平面上一條分段線性的閉曲線。也就是說，多邊形是由一系列首尾相接的直線段組成的。組成多邊形的各直線段稱為該多邊形的邊。多邊形相接兩條邊的連接點稱為多邊形的頂點。若多邊形的邊之間除了連接頂點外沒有別的公共點，則稱該多邊形為簡單多邊形。一個簡單多邊形將平面分為3個部分：被包圍在多邊形內的所有點構成了多邊形的內部；多邊形本身構成多邊形的邊界；而平面上其余的點構成了多邊形的外部。當一個簡單多邊形及其內部構成一個閉凸集時，稱該簡單多邊形為凸多邊形。也就是說凸多邊形邊界上或內部的任意兩點所連成的直線段上所有的點均在該凸多邊形的內部或邊界上。 通常，用多邊形頂點的逆時針序列來表示一個凸多邊形，即P=表示具有n條邊v0v1，v1v2，… ,vn-1vn的一個凸多邊形，其中，約定v0=vn 。 若vi與vj是多邊形上不相鄰的兩個頂點，則線段vivj稱為多邊形的一條弦。弦 將多邊形分割成凸的兩個子多邊形和。多邊形的三角剖分是一個將多邊形分割成互不重迭的三角形的弦的集合T。如圖是一個凸多邊形的兩個不同的三角剖分。 凸多邊形最優三角剖分的問題是：給定一個凸多邊形P=以及定義在由多邊形的邊和弦組成的三角形上的權函數ω。要求確定該凸多邊形的一個三角剖分，使得該三角剖分對應的權即剖分中諸三角形上的權之和為最小。 可以定義三角形上各種各樣的權函數W。例如：定義ω(△vivjvk)=|vivj|+|vivk|+|vkvj|，其中，|vivj|是點vi到vj的歐氏距離。相應于此權函數的最優三角剖分即為最小弦長三角剖分。(注意：解決此問題的算法必須適用于任意的權函數) 4． 防衛導彈 一種新型的防衛導彈可截擊多個攻擊導彈。它可以向前飛行，也可以用很快的速度向下飛行，可以毫無損傷地截擊進攻導彈，但不可以向后或向上飛行。但有一個缺點，盡管它發射時可以達到任意高度，但它只能截擊比它上次截擊導彈時所處高度低或者高度相同的導彈。現對這種新型防衛導彈進行測試，在每一次測試中，發射一系列的測試導彈（這些導彈發射的間隔時間固定，飛行速度相同），該防衛導彈所能獲得的信息包括各進攻導彈的高度，以及它們發射次序。現要求編一程序，求在每次測試中，該防衛導彈最多能截擊的進攻導彈數量，一個導彈能被截擊應滿足下列兩個條件之一： a)它是該次測試中第一個被防衛導彈截擊的導彈； b)它是在上一次被截擊導彈的發射后發射，且高度不大于上一次被截擊導彈的高度的導彈。 輸入數據：第一行是一個整數n，以后的n各有一個整數表示導彈的高度。 輸出數據：截擊導彈的最大數目。 5． 石子合并 在一個圓形操場的四周擺放著n堆石子(n<= 100)，現要將石子有次序地合并成一堆。規定每次只能選取相鄰的兩堆合并成新的一堆,并將新的一堆的石子數,記為該次合并的得分。編一程序，由文件讀入堆棧數n及每堆棧的石子數(<=20)。 選擇一種合并石子的方案,使得做n－1次合并,得分的總和最小； 輸入數據： 第一行為石子堆數n； 第二行為每堆的石子數,每兩個數之間用一個空格分隔。 輸出數據： 從第一至第n行為得分最小的合并方案。第n+1行是空行.從第n+2行到第2n+1行是得分最大合并方案。每種合并方案用n行表示，其中第i行(1<=i<=n)表示第i次合并前各堆的石子數(依順時針次序輸出，哪一堆先輸出均可)。要求將待合并的兩堆石子數以相應的負數表示。 Sample Input 4 4 5 9 4 Sample Output －4 5 9 －4 －8 －5 9 －13 －9 22 4 －5 －9 4 4 －14 －4 －4 －18 22 6． 最小代價子母樹 設有一排數，共n個，例如：22 14 7 13 26 15 11。任意2個相鄰的數可以進行歸并，歸并的代價為該兩個數的和,經過不斷的歸并，最后歸為一堆，而全部歸并代價的和稱為總代價，給出一種歸并算法，使總代價為最小。 輸入、輸出數據格式與“石子合并”相同。 Sample Input 4 12 5 16 4 Sample Output －12 －5 16 4 17 －16 －4 －17 －20 37 7． 商店購物 某商店中每種商品都有一個價格。例如，一朵花的價格是2 ICU(ICU 是信息學競賽的貨幣的單位）；一個花瓶的價格是5 ICU。為了吸引更多的顧客，商店提供了特殊優惠價。特殊優惠商品是把一種或幾種商品分成一組。并降價銷售。例如：3朵花的價格不是6而是5 ICU；2個花瓶加1朵花是10 ICU不是12 ICU。 編一個程序，計算某個顧客所購商品應付的費用。要充分利用優惠價以使顧客付款最小。請注意，你不能變更顧客所購商品的種類及數量，即使增加某些商品會使付款總數減小也不允許你作出任何變更。假定各種商品價格用優惠價如上所述，并且某顧客購買物品為：3朵花和2個花瓶。那么顧客應付款為14 ICU因為： 1朵花加2個花瓶優惠價：10 ICU 2朵花正常價：4 ICU 輸入數據：第一個文件INPUT．TXT描述顧客所購物品（放在購物筐中）;第二個文件描述商店提供的優惠商品及價格（文件名為OFF ER．TXT）。 兩個文件中都只用整數。 第一個文件INPUT．TXT的格式為:第一行是一個數字B（0≤B≤5），表示所購商品種類數。下面共B行，每行中含3個數C，K，P。 C 代表商品的編碼（每種商品有一個唯一的編碼），1≤C≤999。K代表該種商品購買總數，1≤K≤5。P 是該種商品的正常單價（每件商品的價格），1≤P≤999。請注意，購物筐中最多可放5*5＝25件商品。 第二個文件OFFER．TXT的格式為:第一行是一個數字S（0≤S≤9 9），表示共有S 種優惠。下面共S行，每一行描述一種優惠商品的組合中商品的種類。下面接著是幾個數字對（C，K），其中C代表商品編碼，1≤C≤9 99。K代表該種商品在此組合中的數量，1≤K≤5。本行最后一個數字P（1≤ P≤9999）代表此商品組合的優惠價。當然， 優惠價要低于該組合中商品正常價之總和。 輸出數據：在輸出文件OUTPUT．TXT中寫 一個數字（占一行），該數字表示顧客所購商品（輸入文件指明所購商品）應付的最低貨款。 8． 旅游預算 一個旅行社需要估算乘汽車從某城市到另一城市的最小費用，沿路有若干加油站，每個加油站收費不一定相同。旅游預算有如下規則： 若油箱的油過半，不停車加油，除非油箱中的油不可支持到下一站；每次加油時都加滿；在一個加油站加油時，司機要花費2元買東西吃；司機不必為其他意外情況而準備額外的油；汽車開出時在起點加滿油箱；計算精確到分（1元=100分）。編寫程序估計實際行駛在某路線所需的最小費用。 輸入數據：從當前目錄下的文本文件“route.dat”讀入數據。按以下格式輸入若干旅行路線的情況： 第一行為起點到終點的距離（實數） 第二行為三個實數，后跟一個整數，每兩個數據間用一個空格隔開。其中第一個數為汽車油箱的容量（升），第二個數是每升汽油行駛的公里數，第三個數是在起點加滿油箱的費用，第四個數是加油站的數量。（〈=50）。接下去的每行包括兩個實數，每個數據之間用一個空格分隔，其中第一個數是該加油站離起點的距離，第二個數是該加油站每升汽油的價格（元/升）。加油站按它們與起點的距離升序排列。所有的輸入都有一定有解。 輸出數據：答案輸出到當前目錄下的文本文件“route.out”中。該文件包括兩行。第一行為一個實數和一個整數，實數為旅行的最小費用，以元為單位，精確到分，整數表示途中加油的站的N。第二行是N個整數，表示N個加油的站的編號，按升序排列。數據間用一個空格分隔，此外沒有多余的空格。 Sample Input 516.3 38.09 1 15.7 22.1 20.87 3 2 125.4 1.259 297.9 1.129 345.2 0.999 Sample Output 38.09 1 2

回答者：韓國女排金延璟2016-08-27 00:00