題目： UVa - 357 - Let Me Count The Ways 題目說明有面額 [1, 5, 10, 25, 50] 的錢幣，給一個 n，求 n 有幾種不同的組合方式。 Input： 每行為一組測資，一個整數表示 n。 Output： 輸出 n 有幾種不同的組合方式。 解題思路DP 的 Coin Change 問題，核心概念為枚舉每一個最後加入的面額。 參考解法1234567891011121314151617181920212223242526272829303132333435363738#include <bits/stdc++.h>using namespace std;static auto __ = []{ ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); return 0;}();long long money[] = { 1, 5, 10, 25, 50 };long long dp[30001];void CoinChan ...

課程名稱：演算法概論 CS309 B授課教師：林基成發放時間：2021-04-01截止時間：2021-04-08 題目說明這次的作業是 UVa 中的 3 題題目，與 Dynamic Programming - Floyd Warshall’s Algorithm 有關。 UVa 821 - Page Hopping：UVa - 821 解題紀錄 UVa UVa - 10171 - Meeting Prof. Miguel…：UVa - 10171 解題紀錄 UVa 11463 - Commandos：UVa - 11463 解題紀錄

題目： UVa - 11463 - Commandos 題目說明給一個無向圖，每條邊的 cost 皆為 1，給一個起點及終點，求從起點到某一點後再到終點所需要的最大 cost。 Input： 第一個整數 T，表示有 T 組測資，每組測資前兩個數字為 n、m，依序表示圖上有 n 個點 ( 0 ~ n - 1 )，及 m 條邊，後面 m 行，每行有兩個整數 u、v，表示 u、 v 兩點是連通的。 Output： 輸出從起點到某一點後再到終點所需要的最大 cost。 解題思路All Pair Shortest Path 題，讀測資並做 Floyd-Warshall Algorithm 求解即可。 參考解法12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455565758596061626364656667#include <bits/stdc++.h>using namespace std;// reference: https:// ...

題目： UVa - 10171 - Meeting Prof. Miguel… 題目說明給兩個圖 M、Y，圖上的點相同，但相通的邊不同，每條邊都有各自的 cost，兩個人各自在圖上走，各自給一個起點，求兩者可相遇且兩人的 cost 總和最小的 cost 及相遇的點，若最小 cost 的點有多個需要全部輸出。 Input： 每組測資第一個數字 m，表示有 m 行資料，每行資料為四個字符及一個數字組成，依序為 a、b、u、v、w，a 表示該行測資是哪個圖上的，b 表示該邊為單向或雙向 ( B 為雙向 )，u、v、w 依序為邊上兩點及 cost。 Output： 輸出兩者可相遇且兩人的 cost 總和最小的 cost 及相遇的點，若最小 cost 的點有多個需要全部輸出。 解題思路All Pair Shortest Path 題，讀測資並做 Floyd-Warshall Algorithm 求解即可。需要注意的是測資給的邊可能有重複，此時取 cost 較小者。 參考解法12345678910111213141516171819202122232425262728293031323334353 ...

題目： UVa - 821 - Page Hopping 題目說明給一個有向圖，求所有可連通的任意兩點的最短路徑平均。 Input： 每組測資裡面有許多兩個數字的 pair，u、v，表示點 u 與點 v 連通，若皆為 0 表示該組測資結束，若測資的第一組 u、v 皆為 0 表程式結束。 Output： 輸出所有可連通的任意兩點的最短路徑平均。 解題思路All Pair Shortest Path 題，讀測資並做 Floyd-Warshall Algorithm 求解即可。需要注意的是點的編號並不是集中的，所以需要紀錄點的最大編號。 參考解法123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566#include <bits/stdc++.h>using namespace std;// reference: https://ppt.cc/f6R74xstatic auto __ = [] ...

課程名稱：演算法概論 CS309 B授課教師：林基成發放時間：2021-03-27截止時間：2021-04-03 題目說明這次的作業是 UVa 中的 3 題題目，與 Dynamic Programming - Max 2D/3D Range Sum 有關。 UVa 10827 - Maximum sum on a torus：UVa - 10827 解題紀錄 UVa 11951 - Area：UVa - 11951 解題紀錄 UVa 10755 - Garbage Heap：UVa - 10755 解題紀錄

題目： UVa - 10755 - Garbage Heap 題目說明給一個 A * B * C 的長方體，長方體內每個單位都有數字，求最大的子長方體的數字和。 Input： 第一個整數為 T，表示有 T 組測資，每組測資前三個整數依序為 A、B、C，後面 A * B * C 個數字為長方體內單位的數字。 Output： 輸出最大的子長方體的數字和。 解題思路Kadane’s Algorithm 題，依照二維壓成一維的概念將三維壓成二維，再將二維壓成一維之後使用 Kadane’s Algorithm 求解即可。 參考解法123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384#include <bits/stdc++.h>using namespace std;static auto __ = []{ ...

題目： UVa - 11951 - Area 題目說明給一個 N * M 的矩陣，矩陣上有一些數字，求最大的子矩陣面積，且子矩陣和不可超過 K。若有相同面積的子矩陣，取子矩陣和最小的那個子矩陣和。 Input： 第一個整數為 T，表示有 T 組測資，每組測資前三個整數依序為 N、M、K，後面 N * M 個整數為矩陣中的數字。 Output： 求最大的子矩陣面積，且子矩陣和不可超過 K。 解題思路Kadane’s Algorithm 題，將二維壓成一維之後使用 Kadane’s Algorithm 求解即可。 由於有不可超過 K 的限制，且要求的是子矩陣的最大面積，因此修改一下，l 為左端點，遍歷到的 sum[i] 視為右端點，當總和超過 K 時不斷將左端點往左移，接著計算面積即可。 參考解法1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556575859606162636465666768697071#include <bit ...

題目： UVa - 10827 - Maximum sum on a torus 題目說明給一個 N * N 的矩陣，矩陣上有一些數字，求最大的子矩陣和，子矩陣可跨過邊界。 Input： 第一個整數為 T，表示有 T 組測資，每組測資第一個整數為 N，後面 N * N 個數字為矩陣中的數字。 Output： 求最大的子矩陣和，子矩陣可跨過邊界。 解題思路Kadane’s Algorithm 題，將二維壓成一維之後使用 Kadane’s Algorithm 求解即可。 由於可跨過邊界，所以先將資料複製，將 N * N 複製為 2N * N，第 N 列與第 0 列相同，第 N + 1 列與第 1 列相同，…。如此可解決跨越上下的情況，而跨左右的子矩陣可視為整個矩陣減去最小子矩陣。 參考解法123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778#inclu ...

課程名稱：演算法概論 CS309 B授課教師：林基成發放時間：2021-03-15截止時間：2021-03-22 題目說明這次的作業是 UVa 中的 3 題題目，與 Dynamic Programming - 0-1 Knapsack 有關。 UVa 1213 - Sum of Different Primes：UVa - 1213 解題紀錄 UVa 10616 - Divisible Group Sums：UVa - 10616 解題紀錄 UVa 11566 - Let’s Yum Cha!：UVa - 11566 解題紀錄