学校测试-2015-2-27
題目一
描述
關鍵子工程（project.c/cpp/pas）
在大型工程的施工前，我們把整個工程劃分為若干個子工程，并把這些子工程編號為1、2、……、N；這樣劃分之后，子工程之間就會有一些依賴關系，即一些子工程必須在某些子工程完成之后才能施工。由于子工程之間有相互依賴關系，因此有兩個任務需要我們去完成：首先，我們需要計算整個工程最少的完成時間；同時，由于一些不可預測的客觀因素會使某些子工程延期，因此我們必須知道哪些子工程的延期會影響整個工程的延期，我們把有這種特征的子工程稱為關鍵子工程，因此第二個任務就是找出所有的關鍵子工程，以便集中精力管理好這些子工程，盡量避免這些子工程延期，達到用最快的速度完成整個工程。為了便于編程，現在我們假設：
（1）根據預算，每一個子工程都有一個完成時間。
（2）子工程之間的依賴關系是：部分子工程必須在一些子工程完成之后才開工。
（3）只要滿足子工程間的依賴關系，在任何時刻可以有任何多個子工程同時在施工，也既同時施工的子工程個數不受限制。
（4）整個工程的完成是指：所有子工程的完成。
輸入數據
第1行為N，N是子工程的總個數，N≤200。
第2行為N個正整數，分別代表子工程1、2、……、N的完成時間。
第3行到N+2行，每行有N-1個0或1。其中的第I+2行的這些0，1，分別表示“子工程I”與子工程1、2、…、I-1、I+1、…N的依賴關系，（I=1、2、……、N）。每行數據之間均用一個空格分開。
輸出數據：
如子工程劃分不合理，則輸出-1；
如子工程劃分合理，則用兩行輸出：第1行為整個工程最少的完成時間。第2行為按由小到大順序輸出所有關鍵子工程的編號。
分析
如果子工程 A 必須在 B 之后完成, 那么從 B->A 連邊。然后拓撲排序，如果出現環，說明任務無法完成。邊拓撲排序邊邊計算這個結點之前完成的最小時間。記錄它之前最后一個完成的工程和時間。
找到最后完成的任務，根據之前記錄的它之前最后一個完成的工程一層層找到最后一個任務，也就是一條最長路。
- 但是，最長路可能并不只一條，所以可以用 vector 記錄所有的最長路。我第一次嘗試這樣做。詳見代碼。
- 后來看題解發現可以在最后去找關鍵路徑而不是在一開始拓撲排序就記錄關鍵路徑。這樣可以省很多事。
代碼
https://code.csdn.net/snippets/608610
題目二
描述
機器分配（machine.c/cpp/pas）
某總公司擁有高效生產設備M臺，準備分給下屬的N個分公司。各分公司若獲得這些設備，可以為總公司提供一定的盈利。問：如何分配這M臺設備才能使國家得到的盈利最大？求出最大盈利值。
分配原則：每個公司有權獲得任意數目的設備，但總臺數不得超過總設備數M。其中M<=100，N<=100。
輸入數據：
第一行為兩個整數M，N。接下來是一個N×M的矩陣，其中矩陣的第i行的第j列的數Aij表明第i個公司分配j臺機器的盈利。所有數據之間用一個空格分隔。
輸出數據：
只有一個數據，為總公司分配這M臺設備所獲得的最大盈利。
分析
- DP
- f[i][j]表示前 i 個公司分到 j 臺機器的最大盈利
- f[i][j] = max{f[i][j], f[i-1][j-k] + A[i][k](0≤k≤j)}
- f[n][m]
代碼
https://code.csdn.net/snippets/608633
題目三
描述
編輯距離(edit.c/cpp/pas)
字符串是數據結構和計算機語言里很重要的數據類型，在計算機語言中，對于字符串我們有很多的操作定義，因此我們可以對字符串進行很多復雜的運算和操作。實際上，所有復雜的字符串操作都是由字符串的基本操作組成。例如，把子串a替換為子串b，就是用查找、刪除和插入這三個基本操作實現的。因此，在復雜字符串操作的編程中，為了提高程序中字符操作的速度，我們就應該用最少的基本操作完成復雜操作。
在這里，假設字符串的基本操作僅為：刪除一個字符、插入一個字符和將一個字符修改成另一個字符這三種操作。
我們把進行了一次上述三種操作的任意一種操作稱為進行了一步字符基本操作。
下面我們定義兩個字符串的編輯距離：對于兩個字符串a和b，通過上述的基本操作，我們可以把a變成b或b變成a；那么，把字符串a變成字符串b需要的最少基本字符操作步數稱為字符串a和字符串b的編輯距離。
例如，如a=“ABC”，b=“CBCD”，則a與b的編輯距離為2。
你的任務就是：編一個最快的程序來計算任意兩個字符串的編輯距離。
輸入數據：
第1行為字符串a；第2行為字符串b。注：字符串的長度不大于1000，字符串中的字符全為大寫字母。
輸出數據：
編輯距離。
分析
- DP
- f[i][j]表示 a 的前 i 個字符和 b 的前 j 個字符匹配的最小編輯距離
- 初始化：
f[i][0] = i // 表示將前 i 個全部刪除
f[0][i] = i // 表示在 a 中插入 b 的前 i 個 - 修改
f[i][j] = f[i-1][j-1] + (A[i-1] == B[j-1] ? 0 : 1)
// A, B 是字符串，以 0 開始做下標 - 插入
f[i][j] = min(f[i][j], f[i][j-1] + 1) 刪除
f[i][j] = min(f[i][j], f[i-1][j] + 1)f[strlen(A)][strlen(B)]
代碼
https://code.csdn.net/snippets/608645
題目四
描述
在現實生活中，我們經常遇到硬幣找零的問題，例如，在發工資時，財務人員就需要計算最少的找零硬幣數，以便他們能從銀行拿回最少的硬幣數，并保證能用這些硬幣發工資。我們應該注意到，人民幣的硬幣系統是100，50，20，10，5，2，1，0.5，0.2，0.1，0.05，0.02，0.01元，采用這些硬幣我們可以對任何一個工資數用貪心算法求出其最少硬幣數。
但不幸的是：我們可能沒有這樣一種好的硬幣系統，因此用貪心算法不能求出最少的硬幣數，甚至有些金錢總數還不能用這些硬幣找零。例如，如果硬幣系統是40，30，25元，那么37元就不能用這些硬幣找零；95元的最少找零硬幣數是3。又如，硬幣系統是10，7，5，1元，那么12元用貪心法得到的硬幣數為3，而最少硬幣數是2。
你的任務就是：對于任意的硬幣系統和一個金錢數，請你編程求出最少的找零硬幣數；如果不能用這些硬幣找零，請給出一種找零方法，使剩下的錢最少。
輸入數據：
第1行，為N和T，其中1≤N≤500為硬幣系統中不同硬幣數；1≤T≤10000為需要用硬幣找零的總數。
第2行為N個數值不大于65535的正整數，它們是硬幣系統中各硬幣的面值。
輸出數據：
如T能被硬幣系統中的硬幣找零，請輸出最少的找零硬幣數。
如T不能被硬幣系統中的硬幣找零，請輸出剩下錢數最少的找零方案中的所需的最少硬幣數。
分析
- 完全背包
- f[i]表示找錢數為 i 時最少的硬幣數量。
- f[i] = min{f[i], f[i-A[j]] + 1(A[j]≤i)} // 注意判斷
- f[t]
- 如果f[t] == INF，從 t 向前找到第一個不為INF的值f[t1]，t - t1就是找零后剩下的最小錢數。
- 什么是找零后剩下的最小錢數？找回的錢比設定要少（覺得十分不合理…），讓這個差值盡可能小
代碼
https://code.csdn.net/snippets/608653
- 改了好幾遍才都改對，以上代碼都可以 AC 了。
- 各種細節 :
- STL的unique并不真正把重復的元素刪除，是把重復的元素移到后面去了。返回一個迭代器，它自己和其后的元素都是原來重復的元素
- 數組越界的判定
- DP時的條件判定
- INF = 0x3f3f3f3f, memset(0x3f) 的寫法可以放心用。致謝 Archon
- 。。。
總結
以上是生活随笔為你收集整理的学校测试-2015-2-27的全部內容，希望文章能夠幫你解決所遇到的問題。
- 上一篇： CODEVS-3303-翻转区间
- 下一篇： [总结] 平衡树总结