題目： UVa - 10003 - Cutting Sticks 題目說明有一個可以切割木頭的工作台，若切割長度為 l 的木頭則需要消耗成本 l，且只能切割一個點，給一個木頭的長度及一些切割點，求將所有切割點都切割所需要的最小總成本。 Input： 每組測資第一個整數為 l，為要切割的木頭總長度，若為 0 表結束。後面一個整數 n，表有 n 個切割點，後面 n 個整數為切割點距離起始點的長度。 Output： 輸出將所有切割點都切割後的最小成本。 解題思路我國文不太好，這題不知道怎麼用文字解釋，其實我也看不懂我在寫啥，建議直接看這篇比較快。 動態規劃題。 先讀取測資，使用 cut 數組儲存所有切割點，並將 l 放在最後面，0 放在最前面，為了方便，先在這裡將 n + 1。 定義 dp[i][j] 表切割 切割點 i ( cut[i] ) 及 切割點 j ( cut[j] ) 中所有切割點的最小花費。 核心概念為，先從最小塊的木頭開始切割，找出最小塊的木頭需要消耗的成本，以此來算出大塊的木頭需要消耗的成本，將程式碼具體化來說，以 Sample I/O 的第一組測資舉例： 123410 ...

課程名稱：演算法概論 CS309 B授課教師：林基成發放時間：2021-02-23截止時間：2021-03-02 題目說明這次的作業是 UVa 中的 3 題題目，與 Dynamic Programming 有關。 UVa 10337 - Flight Planner：UVa - 10337 解題紀錄 UVa 10721 - Bar Codes：UVa - 10721 解題紀錄 UVa 10943 - How do you add?：UVa - 10943 解題紀錄

題目： UVa - 10943 - How do you add? 題目說明給兩個整數 N、K，求將 N 拆為 K 個小於等於 N 的數字相加的所有情況數。不同排序視為不同情況，如 20 + 0，0 + 20 為兩種情況。 題目看不是很懂，好像計算的時候要隨時取 1000000 的餘數。 Input： 每組測資有兩個整數，依序為 N、K，若 N、K 皆為 0 表結束。 Output： 輸出將 N 拆為 K 個小於等於 N 的數字相加的所有情況數。 解題思路動態規劃題，由於測資範圍不大，因此先算出所有情況的答案再輸出即可。 定義 dp[i][j] 表 i 拆成 j 個數字的方法數，先設定初始狀態，dp[i][1] = 1, 對於所有 0 <= i < 101，因為任何數拆成一個數字相加只會有一個情況，就是自己。 對於 dp[i][j]:dp[i][j] = (dp[i][j] + dp[i - k][j - 1]) % 1000000，對於所有 0 <= k <= i。可以想像為，將 i 拆為 k 及 i - k 相加，而 i - k 由 j - 1 個數字相 ...

題目： UVa - 10721 - Bar Codes 題目說明組成 bar 的單位為長方條 ( units )，units 的顏色可以是黑色也可以是白色，同一種顏色排在一起視為一個 bar。 BC(n, k, m) 表總共使用 n 個 units，組成 k 個 bar，每個 bar 的寬度不可超過 m 個 units，且第一個 bar 為黑色，能組出的所有情況數 給 n、k、m，求 BC(n, k, m)。 Input： 每組測資有三個整數，依序為 n、k、m。 Output： 輸出 BC(n, k, m)。 解題思路動態規劃題，由於測資範圍不大，因此先算出所有情況的答案再輸出即可。 定義 dp[n][k][m] 表 BC(n, k, m)，先設定初始狀態，由於第一個 bar 必為黑色，因此可以知道，dp[n][1][m] = 1，對於所有 m >= n，也就是只能是黑色的 bar，而 m >= n 是因為當 m < n 時無法使用完 n 個 units，因此為 0。 對於 dp[n][k][m]： 若 m > n，dp[n][k][m] = dp[n] ...

題目： UVa - 10337 - Flight Planner 題目說明在一個平面座標系上，有一架飛機從原點 ( 0, 0 ) 起飛，要到 X ( X, 0 )，將原點到 X 每 100 miles 分為一段，給每段的各個空層 ( 共 9 層 ) 的風速，飛機每飛過 100 miles 可以選擇往上一層、往下一層、或是平飛，花費的燃料依序為 60、20、30，且花費的燃料還要減掉該層的風速，求從起點到終點花費的最少燃料為何。飛機不能在地面平飛 ( 第 0 層 )，也不能飛超過第 9 層。 Input： 第一個整數 T，表示有 T 組測資，每組測資第一個整數為 X，後面 9 * X / 100 的表格為風速，以左下角為原點，向右為 x 軸 ( 0 ~ X / 100 )，向上為 y 軸 ( 0 ~ 9 )。 Output： 輸出從起點到終點的最小花費燃料。 解題思路動態規劃題，先讀取測資，將每 100 miles 分為一段，winds[i][j] 表第 i 段，第 j 層的風速，先讀取風速，記得是從第 9 層開始。 定義 dp[i][j] 表飛機到達第 i 段，第 j 層所需的最小花費 ...

題目： UVa - 11498 - Division of Nlogonia 題目說明給一個參考點及一些座標，以參考點為原點，求其他座標位於參考點的哪個方向 ( 東北、西北、東南、西南 )，若座標位於 x 軸或 y 軸上則輸出 "divisa"。 Input： 每組測資第一個整數 T，表示有 T 個點，若 T 為 0 表示結束。接下來兩個整數 N、M 表參考點的座標，後面 T 行，每行兩個數字，為要求方向的座標。 Output： 輸出座標相對於參考點的方向。 解題思路讀取測資並根據題目要求判斷即可。 參考解法1234567891011121314151617181920212223242526272829303132#include <bits/stdc++.h>using namespace std;static auto __ = []{ ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); return 0;}();int main(){ ...

題目： UVa - 165 - Stamps 題目說明給兩個整數 h、k，分別代表最多能貼 h 張郵票，及最多能使用 k 種面額的郵票，求最多能組出從 1 開始數到多少的價格。 如 1 3 -> 7，表示使用面額 1 和 3 的郵票，可以組出 1 ~ 7 這 7 種價格。 Input： 每行兩個整數，分別代表 h、k，若皆為 0 表示結束。 Output： 輸出選取的 k 種面額，及最多能組出從 1 開始數到多少的價格。 解題思路由於數據量較少，所以暴力法模擬即可。 先模擬出 k 個面額，stamp 儲存目前模擬的面額，maxVal[i] = d 表示 i + 1 張郵票能組出 1 ~ d 的價格，第一個面額一定是 1 也就是 stamp[0] = 1，而 maxVal[0] 一定是 h，由於我們的目標是組出 1 ~ 多少的價格，因此後面的金額範圍為 stamp[i - 1] + 1 ~ maxVal[i - 1] + 1，依此想法做 DFS 模擬出 k 個面額，而 maxVal 也是使用 DFS 取得。 最後根據題目要求輸出答案即可。 參考解法123456789101112 ...

題目： UVa - 1746 - String Theory 題目說明給一些整數表示括號的個數，求最大的 k 值。 k-quotation 的定義為: 若 k = 1，表示字串頭尾各有一個 ' 號，而中間沒有任何 ' 號。 若 k >= 2，表示字串頭尾各有 k 個 ' 號，而中間是 k-1-quotation。 如 ''All 'work' and no 'play'''，最外層的 ' 號為 2 個，而中間的字串為 1 個，則 k = 2。 解釋的不是很好，可能看題目原文會比較好理解。 For k > 1, a k-quotation is a string that begins with k quote characters, ends with another k quote characters and contains a nested string in-between. The nested string is a non-empty sequence ...

題目： UVa - 615 - Is It A Tree? 題目說明給一個有向圖，求該圖是否是一個 Tree。 根據題目的敘述，Tree 需要滿足以下三個條件: 只有一個沒有被其他節點接入的節點，稱為 root 除了 root 以外的所有節點，都只會被一個邊接入 從根到任一節點，都只有一條唯一的路徑 Input： 每組測資包含許多組邊，每組邊以兩個整數表示，u、v 表示有一條 u 指向 v 的邊，若為 0 0 表示此組測資結束，若一組測資以 -1 -1 開始表示程式結束。 Output： 輸出該組測資是否是一個 Tree。 解題思路建圖，先判斷是否沒有任何節點，若沒有任何節點也是 Tree，否則隨便挑一個沒有被接入的節點開始 DFS 判斷是否有環，最後判斷是否所有節點都有被遍歷到即可。 參考解法123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767 ...

題目： UVa - 10267 - Graphical Editor 題目說明實作一個模擬圖像編輯的程式，根據指令做出對應的操作。 解題思路根據題目的表格做出對應的操作即可，需要注意的是，題目的 X1、X2 和 Y1、Y2，並沒有設定誰大誰小，所以要記得判斷。填色則使用 DFS 即可，注意邊界條件。 參考解法123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106#include <bits/stdc++.h>using namespace std;static auto __ = []{ ios_base::sync_with_stdio(0); cin.tie(0); cout.t ...