大衞的筆記

題目大意

你爬上了山峰！你想把這個興奮的心情告訴其他還在爬山朋友，但那些朋友都還在山上爬，你要跑下去跟他們說。
現在你想要跟全部的朋友講，下山不需要花很多體力、但是上山需要花體力，但是題目保證一定會有一條完整的路徑(不會經過重複的路)可以讓你可以走到每個朋友的身邊。

現在請你算出你走到每個朋友身邊需要耗費多少體力。
題目連結

題目大意

抽屜櫃是很方便的家具之一，可以放入很多的物品，而且每一個抽屜都可以選擇上鎖或不上鎖，上鎖的抽屜就會相當安全，但要小心，如果 i 抽屜上鎖，i+1抽屜不上鎖，那麼小偷可以透過 i+1 抽屜抽掉後，把 i 的抽屜物品拿走。

我們想請問如果我們給你一個抽屜櫃並且有 n 個抽屜，並要保證 s 個物品安全，想請問一共有幾種做法？
UVa 題目中的 U 表示不上鎖，L 表示上鎖，在 n=6, s=4 的情況下，有六種做法。

題目連結

重點觀念

• 察覺這是一個 3 維 DP
• 理解題目的抽屜，有點不好懂XD
• 透過 DP 來解決各種發生狀態
  • 如果上一層沒鎖，這層有鎖，那要怎麼用 DP 解決。
  • 有可能鎖著的櫃子，比櫃子數量來的更多嗎?

分析

• 首先我們可以確定一定有兩個變數
  • 幾個抽屜、有幾個上鎖
  • 但好像沒有辦法解決，透過 i+1 抽屜抽掉後，把 i 的抽屜物品拿走。這種可能性？
  • 那我們可以試試一種方法來解決這種問題。
  • 增加一個抽屜，都是放到櫃子中的最上層，我們每次都只判斷最上層的櫃子有沒有鎖；如此一來，就解決中間櫃子有沒有鎖的問題，因為中間的櫃子一定都是透過其他的櫃子累加上來的。
• 因此我們就再增加一個變數，最上層的櫃子有沒有鎖？
• dp[i][j][k]
  • i 是抽屜
  • j 是物品可置放在安全抽屜的個數，簡稱可靠抽屜
    注意：可靠抽屜並不是鎖，但有可靠抽屜才會有鎖
  • k 是最上層有沒有上鎖，1 表示有、0 表示沒有。
• 那就準備進行 DP 規劃拉，我們來看看 DP 的狀態轉移
  • 先找出最初的設定值
    • dp[1][0][0] = 1，在 1 個櫃子、0 個可靠抽屜的情況下有一種做法，合理！
      0 個櫃子、0 個可靠抽屜，則不合理。這樣並不符合題目要求。
    • dp[1][1][1] = 1，1 個櫃子、1 個可靠抽屜的情況下只有一種作法，合理！
      • 0 個櫃子、1 個可靠抽屜，則不合哩，你沒有櫃子，可靠抽屜有甚麼用阿XD。
      • dp[1][0][1] = 1，1 個櫃子、0 個可靠抽屜的情況下最上層的櫃子是所住的，不合理！
        這裡就是一個很明顯的範例點，由於 n=1 因此最上層就是其本身，但是沒有鎖怎麼會有可靠抽屜呢，因此這是很明顯的錯誤
  • 得出結論，抽屜的數量必須要大於鎖的數量
  • 狀態轉移公式
    • dp[i][0][0] = dp[i-1][0][0] + dp[i-1][1][1]
      • 需要特別注意，可能有些人會搞不懂為甚麼這裡也要加 dp[i-1][1][1]
        因為在 dp[i][0][0] 情況下，最上層的櫃子是沒有鎖的，此時 dp[i-1][1][1] 則是有鎖，但現在最上層加了一層沒鎖的抽屜，那第二層有鎖也是白鎖。
      • 因此我們的可靠抽屜必須 -1
    • dp[i][j][0] = dp[i-1][j+1][1] + dp[i-1][j][0]
      • 由於 dp[i][j][0] 最上層沒有鎖，因此 dp[i-1][j+1][1] 中安全抽屜會少一(最上層的抽屜有鎖住，勢必可靠抽屜會多一個)，會被人從最上層抽屜拿取上鎖的抽屜。
      • dp[i-1][j][0] 則很合理
    • dp[i][j][1] = dp[i-1][j-1][0] + dp[i-1][j-1][1]
      • dp[i-1][j-1][0] 很合理，現在最上層有鎖，因此安全抽屜會加一
      • dp[i-1][j-1][1]，同上

參考連結

UVa 11420 - Chest of Drawers by pinghenotes

心得

我記得我好像高中，就有寫過這題了XD，而且我印象我想了一個禮拜才寫出這題R….，那時候的我好笨QQ，不過那時候我記得網路上還沒有太多詳解，因此我沒有辦法順利解決這些題目。

現在有了，也讓我學會了！太開心了，趕緊記錄起來

題目程式碼

會在下面放一些簡單註解，供大家學習時參考。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30

#include <iostream>
#include <bits/stdc++.h>
#define LOCAL
#define int long long
#define MAXN 70
using namespace std;
int dp[MAXN][MAXN][2];
int n, s;

int32_t main()
{
#ifdef LOCAL
    freopen("in1.txt", "r", stdin);
    freopen("out.txt", "w", stdout);
#endif // LOCAL
    dp[1][0][0] = 1; //註解 4-1-1
    dp[1][1][1] = 1; //註解 4-1-2 
    for(int i = 2; i < MAXN-2; i++){
        dp[i][0][0] = dp[i-1][0][0] + dp[i-1][1][1]; //註解 4-3-1
        for(int j = 1; j <= i; j++){
            dp[i][j][0] = dp[i-1][j+1][1] + dp[i-1][j][0]; //註解 4-3-2
            dp[i][j][1] = dp[i-1][j-1][0] + dp[i-1][j-1][1]; //註解 4-3-3
        }
    }
 
    while(cin >> n >> s && n >= 0 && s >= 0){
        cout << dp[n][s][0] + dp[n][s][1] << "\n"; //輸出答案
    }
    return 0;
}

題目大意

目前正在做林地復育，大家給你一個任務是數每一個樹的其中一個 level 樹幹有幾個，而林地裡面的樹大多邏輯是這樣，觀察下面此圖找到邏輯

邏輯大概如下

• level 1 的樹，只會是一枝樹幹
• level i 的樹，如果這一枝樹幹不是透過上一層分裂而來，那 level i+1 要分裂成兩個樹幹
• level i 的樹，是透過上一層分裂而來，那 level i+1 不分裂

我們會問你 level i，請告訴我們那一層有幾個樹幹

題目大意

題目大意

這個地方有四個硬幣，你必須用 4 個硬幣組合成 v 元，有 q 個查詢，且每個硬幣數量都會隨之 q 不同，想請問在每次的 q 查詢中所設定的硬幣數量內，最多有幾種組合方法

題目連結

題目大意

獨特世界裡面的人開車非常特別，他們從任意一個點出發到另外一個點的成本都是唯一無二的且只有一種走法，因此獨特世界只要看到成本就可以知道這是從 A 到 B 的車票，但獨特世界裡面突然發現了一個大問題，他們發現只要你願意繞路就可以讓任意一個點出發到另外一個點的成本竟然可以有多種解法，且成本不一致！
因此總統下令

• 每一條路徑可以重複走，只有終點與前一個點的路徑只能走一遍
• 不可以走非必要路徑
• 必須讓開車成本符合總統要求的成本

如果可以就輸出 yes、最小使用道路數量，no 表示不行
好了，現在需要一個程式設計師來解決問題了！
注意，每一個 test case 中間要有斷行

題目大意

摩天大樓一座有一座的蓋起，這時候許多摩天大樓在一起時會有一條天際線。
摩天大樓有不同的寬度、高度，我們想要找出 LIS 並且寬度要是最長的、LDS 並且寬度要是最長的

題目連結

題目大意

我們定義 Wavio Sequence

• 長度必須是 \(2 * n + 1\)
• 前 \(n+1\) 個數字必須遞增
• 後 \(n+1\) 個數字必須遞減
  接下來會給你一個數列，請你在這些數字中找出 最長 Wavio Sequence

題目連結

動態規劃 Dynamic programming 介紹

動態規劃用在需要狀態轉移的題目上，例如說 \(y = 2x+1\)，那麼在計算出 y 之前就必須要有 x，否則 y 沒有辦法產生一個自然數。

動態規劃最好的理解方式就是，我們將某些變數的所有可能都列舉出來，並根據我們之前的紀錄，並透過遞迴關係式找出答案。
舉例：\(y = 2x+1\)，我們可以將產生出來的 y，再帶入 x，想請問 y 等於 15 有幾種組合可以產生。

• 遞迴關係式就是 \(y = 2x+1\)
• 我們可以設定一個陣列 dp[x(0~15)] = x 組合的數量
• 現在我們可以做一個迴圈如下

1
2
3

for(int i = 0; i <= 15; i++){
    dp[2*i+1] = dp[i] + 1;
}

• 你跟我說這很像遞迴？對！他就是遞迴的有效率版，浪費記憶體版XD。

下面我們來聊聊一些常用的 dp 問題

題目大意

一群好朋友要去吃港式飲茶，朋友們說好要一起出錢，同時不希望一樣的菜色出現兩次、或是一個人叫兩次以上的點心，看起來很膩，吃不到別的東西。
於是朋友們對每一樣菜列出了自己的喜愛程度，然後交由你來負責點菜，你需要滿足他們的平均最大喜愛程度
其中有 N 位朋友、每位朋友的預算為 x，有 K 個點心，入場費用是 T，並加收 10% 服務費(點心價+入場費)，就靠你幫忙算出拉

題目連結

題目大意

Tobby and Query 對一些事情很感興趣，Tobby 對一些問題很有興趣
題目會給你一組數列，其中數列的數字只會是 0~9，之後會給你一個區間 [l,r]，想問妳這裡面有幾個不重複的數字

題目連結