最佳答案

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