題目： UVa - 11566 - Let’s Yum Cha! 題目說明Unfortunate狗的ACM園地: 11566 - Let’s Yum Cha! 解題思路先算出總共可用的金額，之後 DP 求解即可。 定義 dp[j][k] 表示最多可以選擇 j 盤點心，共有 k 元預算。dp[j][k] = max(dp[j - 1][k - price[i]], max(dp[j - 1][k], dp[j][k]))最後的 dp[j][k] 也要取是因為縮減了一維，原本應為 dp[i][j][k]，縮減的那一維意義為只可選擇前 i 種點心，因此 dp[j][k] 也要放進來比較，意義為若多一種點心可選擇，但滿意度減少，則不如不多該選擇。 由於 DP 縮減了一維，所以計算時要從後面往前算。 參考解法123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263#include <bits/stdc++.h> ...

題目： UVa - 10616 - Divisible Group Sums 題目說明給一些整數及一些 D、M，求在這些整數中，找 M 個相加可以被 D 整除的情況數。 Input： 每組測資前兩個整數依序為 N、Q，表有 N 個數字，及 Q 組 D、M，後面 N 行為 N 個整數，再後面 Q 行每行有兩個整數，依序代表 D、M。 Output： 輸出在這些整數中，找 M 個相加可以被 D 整除的情況數。 解題思路為了方便計算，先對所有數字進行處理，使得數字都落在 0 ~ D - 1 裡面，若是正數只要直接 % D 即可，負數需要特別處理，由於負數 % D 後範圍會落在 0 ~ - ( D - 1 )，根據同餘定理，加上 D 後取餘的結果相同，因此加上 D，使得所有數字都在範圍內。 定義 dp[k][j]，表挑 j 個數字相加等於 k 的情況數。 之後遍歷處理好的陣列，核心想法為考慮目前遍歷的數字是否要加入，以此想法做 DP 即可。 由於 DP 縮減了一維，所以計算時要從後面往前算。 最後再將能被 D 整除的所有情況數相加即可。 參考解法123456789101112131415161 ...

題目： UVa - 1213 - Sum of Different Primes 題目說明給兩個整數 n、k，求將 n 拆為 k 個質數相加的結果有幾種。 Input： 每行兩個整數依序代表 n、k，若皆為 0 表結束。 Output： 輸出將 n 拆為 k 個質數相加的結果有幾種。 解題思路因為 n <= 1120，所以先使用質數篩找出小於等於 1120 的所有質數。 定義 dp[i][j]，表將 i 拆為 j 個質數相加的情況數。 之後 DP，對於 dp[i][j] 來說，dp[i][j] += dp[i - v][j - 1]，對於所有 v 為小於等於 i 的質數。可思考成 v 為最後加入的質數。 由於 DP 縮減了一維，所以計算時要從後面往前算。 參考解法123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051#include <bits/stdc++.h>using namespace std;// reference: http ...

課程名稱：演算法概論 CS309 B授課教師：林基成發放時間：2021-03-07截止時間：2021-03-15 題目說明這次的作業是 UVa 中的 3 題題目，與 Dynamic Programming - Longest Increasing Subsequence 有關。 UVa 481 - What Goes Up：UVa - 481 解題紀錄 UVa 11456 - Trainsorting：UVa - 11456 解題紀錄 UVa 11790 - Murcia’s Skyline：UVa - 11790 解題紀錄

題目： UVa - 11790 - Murcia’s Skyline 題目說明依序給一些建築物的高及重量，求建築物高度嚴格遞增且最寬的寬度，及建築物高度嚴格遞減且最寬的寬度。 Input： 第一個整數 T，表示有 T 組測資，每組測資第一個整數 n，表示有 n 個建築物，後面 n 個數字為建築物的高度，再後面 n 個數字為建築物的寬度。 Output： 輸出 LIS 及 LDS 的寬度，若 LIS 較大則先輸出 LIS，否則先輸出 LDS。 解題思路使用 DP 找出 LIS 及 LDS 即可，記得 LIS[i] 及 LDS[i] 要初始化為 wides[i] 而不是 1。 參考解法1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556575859#include <bits/stdc++.h>using namespace std;static auto __ = []{ ios_base::sync_wit ...

題目： UVa - 11456 - Trainsorting 題目說明d052. 11456 - Trainsorting - 高中生程式解題系統 解題思路weighs[] 存放依序車廂的重量，n 為車廂的總數量，之後遍歷陣列，核心想法為，由於新進的車廂只能放在頭尾，因此當遍歷到第 i 車廂時，若能找出 i 到 n - 1 的最長嚴格遞增子序列 ( Longest Increasing Subsequence ) 的長度及最長嚴格遞減子序列 ( Longest Decrease Subsequence )，就可以找到第一個車廂放 i，能組出的最大車廂重量，因為 LDS 遞減，每個位於 LDS 中的車廂都能放到最前面，而 LIS 遞增，每個位於 LIS 中的車廂都能放到最後面。 有了以上想法後，使用 DP 找出 LIS 及 LDS 即可，記得要從後面開始往前做。 參考解法123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354#include &l ...

題目： UVa - 481 - What Goes Up 題目說明依序給一些數字，找出這些數字的最長嚴格遞增子序列 ( Longest Increasing Subsequence ) 長度及最長嚴格遞增子序列。若有相同長度的 LIS 的話，以選擇後面的元素的 LIS 優先。 Input： 只有一組測資，每行一個整數直到 EOF。 Output： 輸出最長嚴格遞增子序列長度及最長嚴格遞增子序列。 解題思路基本的 LIS 題目，直接讀取數字同時處理，與先讀取後遍歷陣列的意思相同。 每次讀取 nums[i] 後，先在 seq[] 中找到一個最接近且大於等於 nums[i] 的數，並取得其位置 pos，意義為以 nums[i] 做結尾的 LIS 的最大長度為 pos + 1，L 表示目前能夠找到的最大 LIS 長度，因此若 pos == L，表示以 nums[i] 做結尾的 LIS 是目前能夠找到的 LIS 最大長度，因此更新 lastIdx，由於題目要求，若 pos == L - 1 即以 nums[i] 結尾的 LIS 與目前能找到的最長 LIS 的長度相同，因此也要更新 lastIdx ...

課程名稱：演算法概論 CS309 B授課教師：林基成發放時間：2021-02-27截止時間：2021-03-08 題目說明這次的作業是 UVa 中的 3 題題目，與 Dynamic Programming 有關。 UVa 10003 - Cutting Sticks：UVa - 10003 解題紀錄 UVa 10912 - Simple Minded Hashing：UVa - 10912 解題紀錄 UVa 11420 - Chest of Drawers：UVa - 11420 解題紀錄

題目： UVa - 11420 - Chest of Drawers 題目說明d042. 11420 - Chest of Drawers - 高中生程式解題系統 Input： 每組測資有兩個整數，依序為 n、s，若皆小於 0 表結束。 Output： 輸出 n 個櫃子，確保剛好有 s 個櫃子是安全的所有情況數。 解題思路動態規劃題，由於測資範圍不大，因此先算出所有情況的答案再輸出即可。 定義 dp[i][j][k]: 若 k = 0，表有 i 個櫃子，j 個處於安全狀態，且最上層的櫃子沒有鎖。 若 k = 1，表有 i 個櫃子，j 個處於安全狀態，且最上層的櫃子有鎖。 先設定初始狀態 dp[1][0][0] = 1，因為若只有一個櫃子，且櫃子是不安全的，表示只有最上層沒有鎖的這種可能，dp[1][1][1] = 1，因為若只有一個櫃子，且櫃子是安全的，表示只有最上層是有鎖的這種可能。 對於 dp[i][j][k]： 若 k = 0，dp[i][j][0] = dp[i - 1][j + 1][1] + dp[i - 1][j][0]， dp[i - 1][j + 1][1] ...

題目： UVa - 10912 - Simple Minded Hashing 題目說明26 個英文字母，依序從 1 開始編號，a = 1, b = 2, …, z = 26。 給兩個整數 L、S，求使用 L 個英文字母，組成編號總和為 S 的嚴格遞增字串的字串個數。 Input： 每組測資有兩個整數，依序為 L、S。若皆為 0 表結束。 Output： 輸出使用 L 個英文字母，組成編號總和為 S 的嚴格遞增字串的字串個數。 解題思路動態規劃題，由於測資範圍不大，因此先算出所有情況的答案再輸出即可。 由於組成的字串必須是嚴格遞增，因此最多只會有 26 個字母，且編號總和最大為 351 ( 1 + 2 + … + 26 )。 定義 dp[i][j][k] 表只使用前 i 個字母 ( 編號 1 ~ i 的字母 )，組成長度為 j，總和為 k 的字串的所有情況數，先設定初始狀態 dp[n][1][n] = 1，對於所有 1 <= n <= 26，因為若只有一個字母，組成與自己編號總和相同的字串，必定就是只有自己一種情況而已。 對於 dp[i][j][k]： 若 k < ...