題目鏈接

競賽 - 力扣（LeetCode）全球極客摯愛的技術成長平臺

題目解析

A. 3560. 木材運輸的最小成本

AC代碼

class Solution {
public:long long minCuttingCost(int n, int m, int k) {if (n > m) swap(n, m);  // n <= m;using ll = long long;ll ans = 0;if (m > k) {ans = static_cast<ll>(k) * (m - k);}return ans;}
};

思路分析

看完題目后發現，只有三輛車，題目保證有解，意味著最多只有一根木棍的長度會大于k從而被切割。接下來問題轉換為，給定一根長度為n>k的木棍，將其切割為x+y=n兩部分，求z=x*y的最小值。我記得這是初中常見的一個約束，最大值出現在x=y=n/2的位置，最小值出現在兩端。實際上z是x的一個二次函數，在其作用域內先增加后減少。

x的最大值是k，那么z的最小值就是k*(n-k)。

可惜在實現的時候沒注意乘積會導致爆long long。其實返回值是long long就應該注意到的，不太應該。

靈神用Python代碼一行就搞定了。Python的int操作起來是更方便一些。在算法競賽有時會遇到一些大數運算（超過long long范圍的運算），如果用C++需要手動模擬實現，用Python就方便很多。

Python的int類型可以處理任意精度的整數，理論上沒有固定的大小限制，僅受限于計算機的可用內存（RAM）。

B. 3561.移除相鄰字符

AC代碼

class Solution {bool aux(char x, char y) {int diff = abs(x - y);return diff == 1 || diff == 25;}
public:string resultingString(string s) {string stk;for (auto c : s) {if (stk.empty()) {stk.push_back(c);} else {if (aux(stk.back(), c)) {stk.pop_back();} else {stk.push_back(c);}}}return stk;}
};

思路分析

注意到對于每次消除，至多影響前面的一個元素。每次都移除最左邊的字符對，模擬了一下發現類似棧的性質，用棧模擬。

靈神的代碼是先統一入棧，再考慮能否消除，在邏輯和實現上更簡潔一些。

C. 3562. 折扣價交易股票的最大利潤

AC代碼

class Solution {
public:int maxProfit(int n, vector<int>& present, vector<int>& future, vector<vector<int>>& hierarchy, int budget) {vector<vector<int>> graph(n);for (auto &edge : hierarchy) {int u = edge[0] - 1, v = edge[1] - 1;graph[u].push_back(v);}function<vector<vector<int>>(int)> dfs;dfs = [&](int u) -> vector<vector<int>> {vector f(budget + 1, vector<int>(2, 0));vector g = f;for (int v : graph[u]) {auto fv = dfs(v);for (int b = budget; b >= 0; b--) {for (int bv = 0; bv <= b; bv++) {for (int k = 0; k < 2; k++) {g[b][k] = max(g[b][k], g[b - bv][k] + fv[bv][k]);}}}}for (int b = 0; b <= budget; b++) {for (int k = 0; k < 2; k++) {int bu = present[u] / (k + 1);if (bu <= b) {f[b][k] = max(g[b][0], g[b - bu][1] + future[u] - bu);} else {f[b][k] = g[b][0];}}}return f;};return dfs(0)[budget][0];}
};

思路分析

比賽時想到如果員工的關系是一個鏈表，那我可以類似背包問題進行處理，對于每由于每個員工只影響自己的下屬（不會影響領導），所以有無后效性。需要最大化收益，所以有最優子結構。

每個員工有兩個狀態：

• 可以使用的最大費用 $b$
• 領導是否購買股票 $k$：0表示不買，1表示買

維護每個員工$u$在給定狀態$(b,k)$下他和下屬可以獲得的最大收益$f$，$v$表示他的下屬，$c_k$表示在領導買股票狀態為$k$的情況下購買股票的費用，$p_k$表示購買股票的收益。

f u ( b , k ) = m a x { f v ( b , 0 ) , f v ( b ? c k , 1 ) + p k } f_u(b,k)= max\{f_v(b,0), f_v(b-c_k, 1)+p_k\} fu?(b,k)=max{fv?(b,0),fv?(b?ck?,1)+pk?}

然后就可以進行狀態轉移。可是面對一個樹結構，如果某員工決定給$t$個下屬$b$費用讓他們買股票，每個下屬應該用多少費用才能獲得最大收益呢？感覺得再需要一個回溯去搜索，簡單想了一下會超時。

在認真聽了靈神的講解后，發現自己對背包問題的理解還是太淺顯。

現在讓我們專心考慮這個子問題，我們可以先得到每個下屬在所有狀態下的收益$f_v(b,k)$（因為是在DP中），那對于某員工有$b$費用的情況下，我們考慮前$i$下屬消耗多少費用才能獲得最大收益$g_i(b,k)$

之所以考慮前$i$個是因為員工之間的選擇除了消耗費用沒有額外的影響，因此無后效性，求最大收益所以有最優子結構。我們發現，員工對他們下屬的費用選擇形成了一個0-1背包問題，不過與普通背包問題不同的是，每個物品的價格和收益不是固定的，而是一組。

現在問題轉換為，對于某個員工，已經知道前$i?1$個下屬可以獲得的最大收益$g_{i?1}(b,k)$，對第$i$個員工，應該消耗多少費用才能使得$g_i(b,k)$最大，而這是一個貪心問題：

$$g_i(b,k)=\underset{0\le b_v\le b}{\max }{g}_{i?1}(b?b_v,k)+f_{v_i}(b_v,k)$$

在算到所有的$g(b,k)$后，我們就知道了給所有下屬b費用可以得到的最大收益，此時狀態轉移變成了：

f u ( b , k ) = m a x { g v ( b , 0 ) , g ( b ? c k , 1 ) + p k } f_u(b,k)= max\{g_v(b,0), g(b-c_k, 1)+p_k\} fu?(b,k)=max{gv?(b,0),g(b?ck?,1)+pk?}

最后的問題在大的框架上是一個樹型DP，每個節點上葉子到節點的狀態轉移是一個0-1背包問題，在這個0-1背包問題每個物體的選擇上又是一個貪心問題。

經過一段時間的理解我才梳理出整個思路，最后的代碼實現使用了0-1背包的滾動數組優化。自己的思維深度還是不夠，同時也應該梳理思考的順序，把已知、轉換過程都用紙筆記錄下來，可以幫助自己固定思維的結果，否則想著想著都糊涂了，人類的能力真是有局限的啊（迪奧笑）。

D. 3563. 移除相鄰字符后字典序最小的字符串

AC代碼

class Solution {static bool is_pair(char a, char b) {int diff = abs(a - b);return diff == 1 || diff == 25;}
public:string lexicographicallySmallestString(string s) {int n = s.size();vector dp2(n, vector<int>(n, 1));for (int i = 0; i < n; ++i) dp2[i][i] = 0;for (int l = 2; l <= n; ++l) {for (int i = 0; i + l - 1 < n; ++i) {int j = i + l - 1;dp2[i][j] = 0;if (is_pair(s[i], s[j])) {dp2[i][j] = dp2[i + 1][j - 1];if (dp2[i][j]) {continue;}}for (int k = i + 1; k < j; ++k) {dp2[i][j] = (dp2[i][k] && dp2[k + 1][j]);if (dp2[i][j]) {break;}}}}vector<string> dp(n + 1);for (int i = n - 1; i >= 0; --i) {auto &&ans = dp[i];ans.push_back(s[i]);ans.append(dp[i + 1]);for (int j = i + 1; j < n; ++j) {if (dp2[i][j]) {ans = min(ans, dp[j + 1]);}}}return dp[0];}
};

思路分析

比賽的時候沒有看清楚題目，想當然的以為和第二題一樣是從最左邊刪除，然后寫了一通模擬，結果理所當然地過不了。在任意位置刪除相鄰對的情況下，顯然已經不能模擬，只能考慮動態規劃或者貪心。

由于求的是最小的串，所以有最優子結構。可是前面的刪除似乎會影響后面的刪除，這樣看來是有后效性的，似乎看起來應該去思考貪心，但是貪心也沒有很好的想法，起決定作用的是前面的字符，但前面的字符有可能是通過后面的字符會刪除掉。

聽了靈神的講解后發現還是要沉下心去思考。我們上面覺得前面的字符可能和后面的字符配對刪除所以有后效性，但是如果確定刪除了就沒有后效性了。嘗試定義狀態dp[i]為i開始的字符串刪除配對后可以得到的最小字符串，考慮狀態轉移：

• 如果s[i]不刪除，那顯然dp[i] = s[i] + dp[i + 1]

• 關鍵在于s[i]如果可以刪除呢，問題變成了s[i]開始多少個字符可以刪掉。由于n很小，所以我們可以遍歷[i, j]字符串，如果s[i, j]可以刪除，dp[i]= min(dp[i], dp[j])。

  現在問題轉換為，如何快速判斷s[i, j]是否可以刪除。靈神說可以聯想到合法括號字符串（RBS），使用區間DP處理。難點在于，我聯想不到，注意力薄弱。

最終問題通過區間DP處理出哪些區間可以被消除，再用線性DP算出以某個字符開始可以得到的最小字符串。

總結

對這種需要多重轉換組合的問題，一旦卡住就沒法繼續下去。以后對于每個思考的方向，物理化自己的思維過程，把卡住的地方轉換成新的問題重新思考，不要卡住了就想來想去沒有進展。