最佳答案

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

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