# Week 14：動態規劃二

:::info
時間：06/11 9:00 ~ 17:00
地點：成大資工系新館 **65304** 教室
主題：動態規劃二
直播連結：https://youtube.com/live/ROYVq_fj7TU?feature=share
:::

# 必作題題解

[TOC]

## 三章_第五節

### [Kattis rijeci](https://open.kattis.com/problems/rijeci)

撰寫者：Eason

簡單觀察可以發現就是費氏數列

:::spoiler code

#include<bits/stdc++.h>
#define ll long long
#define weakson ios::sync_with_stdio(0), cin.tie(0);
using namespace std;

int main(){
    weakson;

    const int M = 45;

    ll dp[46];
    dp[0] = 0;
    dp[1] = 1;

    for (int i = 2; i <= M; i++){
        dp[i] = dp[i - 1] + dp[i - 2];
    }

    int n;
    cin >> n;

    cout << dp[n - 1] << ' ' << dp[n] << '\n';

    return 0;
}

:::

---

### [A - Frog 1](https://atcoder.jp/contests/dp/tasks/dp_a)

撰寫者：小麥

當青蛙在第一個石頭的時候因為沒有任何的跳躍，所以cost是零，之後第二顆可以先算好，因為要到第二顆一定只能從第一顆跳。
第三顆就可以考慮兩個選項，從第一顆or從第二顆，這裡的最二顆要是dp的第二顆，dp的第二顆在之前的計算就把從第一顆的cost給算進去了。
之後以此類推，四考慮二、三，五考慮三、四。

:::spoiler code

#include <bits/stdc++.h>

using namespace std;

int n;
vector<int> arr;
vector<int> dp;

signed main() 
{
    // ios::sync_with_stdio(0);
    // cin.tie(0);
    // cout.tie(0);

    cin >> n;
    arr.resize(n);
    for (int i = 0; i < n; i++) 
    {
        cin >> arr[i];
    }

    dp.resize(n + 1);
    dp[1] = 0;
    dp[2] = dp[1] + abs(arr[1] - arr[0]);
    for (int i = 3; i <= n; i++) 
    {
        dp[i] = min(abs(arr[i-1] - arr[i-2]) + dp[i-1], abs(arr[i-1] - arr[i-3]) + dp[i-2]);
    }

    cout << dp[n];

    return 0;
}

:::

---

### [Kattis theplank](https://open.kattis.com/problems/theplank)

撰寫者：Eason

題目有說現在只有長度為1、2、3的木頭
所以要接出長度為 n 的木頭
就要從$n-1$、$n-2$、$n-3$的情況取得
可以想成：
>從長度為$n-1$的木頭再接一個長度為 1 的木頭
>從長度為$n-2$的木頭再接一個長度為 2 的木頭
>從長度為$n-3$的木頭再接一個長度為 3 的木頭

因為三種情況最後都只有接一塊木頭
<font color=red>
所以
從長度為 $n-k$ 的木頭再接一個長度為 $k$ 的木頭之情況總和
一定等於 $n-k$ 的情況總和
</font>

因此可以列出轉移式

$dp_i=dp_{i-1}+dp_{i-2}+dp_{i-3}$

:::spoiler code
$$
\begin{cases}
dp_i=0 & i=0 \\
dp_i=1 & i=1 \\
dp_i=2 & i=2 \\
dp_i=4 & i=3 \\
dp_i=dp_{i-1}+dp_{i-2}+dp_{i-3} & i>3
\end{cases}
$$

#include<bits/stdc++.h>
#define ll long long
#define weakson ios::sync_with_stdio(0), cin.tie(0);
using namespace std;

int main(){
    weakson;
    
    const int N = 24;

    ll dp[25];
    dp[0] = 0;
    dp[1] = 1;
    dp[2] = 2;
    dp[3] = 4;

    for (int i = 4; i <= N; i++){
        dp[i] = dp[i - 1] + dp[i - 2] + dp[i - 3];
    }

    int n;
    cin >> n;

    cout << dp[n] << '\n';

    return 0;
}

:::

---

### [Dice Combinations](https://cses.fi/problemset/task/1633/)

撰寫者：小麥

:::spoiler code (迭代)

#include <bits/stdc++.h>

using namespace std;

const int MOD = 1e9 + 7;
int n;
vector<int> dp;

signed main() 
{
    // ios::sync_with_stdio(0);
    // cin.tie(0);
    // cout.tie(0);

    cin >> n;
    dp.resize(n + 1);
    for (int i = 1; i <= min(n, 6); i++)
    {
        dp[i] = 1;
    }
    for (int i = 1; i <= n; i++)
    {
        for (int j = 1; j <= 6; j++)
        {
            if (i <= j)
            {
                break;
            }
            dp[i] += dp[i - j] % MOD;
            dp[i] %= MOD;
        }
    }

    cout << dp[n] << '\n';

    return 0;
}

:::

:::spoiler code (遞迴)

#include <bits/stdc++.h>

using namespace std;

const int MOD = 1e9 + 7;
int n;
vector<int> dp;

int getCombination(int n) 
{
    if (dp[n] != 0)
    {
        return dp[n];
    }

    for (int i = 1; i <= 6; i++)
    {
        if (i > n)
        {
            continue;
        }
        dp[n] += getCombination(n - i);
        dp[n] %= MOD;
    }

    return dp[n];
}

signed main() 
{
    // ios::sync_with_stdio(0);
    // cin.tie(0);
    // cout.tie(0);

    cin >> n;
    dp.resize(n + 1);
    dp[0] = 1;
    dp[1] = 1;
    cout << getCombination(n) << "\n";

    return 0;
} 

:::

---

### [CSES 1635](https://cses.fi/problemset/task/1635/)

撰寫者：Eason

題目給了 $n$ 種面額
所以要湊出金額 $m$
可以從 $m-a_{i} (i=0,1,2,3,...,n)$ 取得
其實跟 [kattis theplank](https://hackmd.io/W_tftCm1SpahIMf8L_xFAQ#Kattis-theplank) 很像
只是那題只有 3 個木頭
而這題有 $n$ 個面額

:::spoiler code

#include<bits/stdc++.h>
#define weakson ios::sync_with_stdio(0),cin.tie(0);
#define ll long long
using namespace std;

const int MAX = 1e9 + 7;

int main(){
    weakson;

    int n, m;
    cin >> n >> m;

    int a[105];
    ll dp[1000005] = {};

    for(int i = 0; i < n; i++){
        cin >> a[i];
    }

    dp[0] = 1;

    for (int i = 1; i <= m; i++){
        for (int j = 0; j < n; j++){
            if (i - a[j] >= 0){
                dp[i] += dp[i - a[j]] % MAX;
                dp[i] %= MAX;
            }
        }
    }

    cout << dp[m] << '\n';

    return 0;
}

:::

---

### [CSES 1638](https://cses.fi/problemset/task/1638/)

撰寫者：小麥

如果一個格子是可以被走的（非地雷），那麼可以到這一格的步數就是從上面走或從左邊走，因此加起來就行了。
如果一個格子是不可以被走的（地雷)，那這一格就是零，因為這一格無論如何都走不到。

:::spoiler code

#include <bits/stdc++.h>

using namespace std;

const int mod = 1e9 + 7;
int n;
vector<vector<int>> arr;
vector<vector<int>> dp;

signed main() 
{
    // ios::sync_with_stdio(0);
    // cin.tie(0);
    // cout.tie(0);

    cin >> n;
    arr.resize(n, vector<int>(n, 0));  
    dp.resize(n + 1, vector<int>(n + 1, 0));

    for (int i = 0; i < n; i++)
    {
        string row;
        cin >> row;
        for (int j = 0; j < n; j++)
        {
            if (row[j] == '*')
            {
                arr[i][j] = 1;
            }
        }
    }

    bool flag = true, flag2 = true;
    for (int i = 1; i <= n; i++)
    {
        if (arr[i-1][0] != 1 && flag)
        {
            dp[i][1] = 1;
        }
        else
        {
            flag = false;
        }
        if (arr[0][i-1] != 1 && flag2)
        {
            dp[1][i] = 1;
        }
        else
        {
            flag2 = false;
        }
    }

    for (int i = 2; i <= n; i++)
    {
        for (int j = 2; j <= n; j++)
        {
            dp[i][j] = dp[i-1][j]  + dp[i][j-1];
            dp[i][j] %= mod;
            if (arr[i-1][j-1] == 1)
            {
                dp[i][j] = 0;
                continue;
            }
        }
    }

    cout << (dp[n][n]) << "\n";

    return 0;
}

:::

---

### [UVa 11067](http://domen111.github.io/UVa-Easy-Viewer/?11067)

撰寫者：Eason

這題的輸出有雷
如果是用 Uva 的
請不要直接複製題目的Sample Output
>題目的Sample Output：

>正確的Output：

<font color = #f9f9f9 >
超可憐，因為這個浪費了整個下午。
</font>

這題數學在學排列組合應該有看過
因為要走捷徑
所以只能往右或往上
基本上對於一個點 $(i,j)$
走到他的所有情況即為
$(i-1,j)$ 的情況加上 $(i,j-1)$ 的情況

可以開一個陣列 $b$
若 $b_{i,j}=1$ 則點 $(i,j)$ 有狼

可以列出轉移式
$$
\begin{cases}
dp_{i,j} = 1 & i == 0 , j == 0 \\
dp_{i,j} = 0 & b_{i,j}==1 \\
dp_{i,j} = dp_{i-1,j} & j == 0 \\
dp_{i,j} = dp_{i,j-1} & i == 0 \\
dp_{i,j} = dp_{i,j-1}+dp_{i-1,j} & otherwise
\end{cases}
$$

:::spoiler code

#include<bits/stdc++.h>
#define ll long long
#define weakson ios::sync_with_stdio(0), cin.tie(0);
using namespace std;

int main(){
    weakson;

    int w, h;
    while (cin >> w >> h){
        if (w == 0 and h == 0) break;

        vector<vector<bool> > wolf (w + 1, vector<bool> (h + 1));

        int n;
        cin >> n;

        while (n--){
            int x, y;
            cin >> x >> y;
            wolf[x][y] = true;
        }

        vector<vector<ll> > dp (w + 1, vector<ll> (h + 1));
        dp[0][0] = 1;

        for (int i = 0; i <= w; i++){
            for (int j = 0; j <= h; j++){

                if ((i == 0 and j == 0) or wolf[i][j]) continue;

                if (i == 0){
                    dp[i][j] = dp[i][j - 1];
                }
                else if (j == 0){
                    dp[i][j] = dp[i - 1][j];
                }
                else{
                    dp[i][j] = dp[i - 1][j] + dp[i][j - 1];
                }
            }
        }

        ll ans = dp[w][h];

        if (ans == 1){
            cout << "There is one path from Little Red Riding Hood's house to her grandmother's house.\n";
        }
        else if (ans == 0){
            cout << "There is no path.\n";
        }
        else{
            cout << "There are " << ans << " paths from Little Red Riding Hood's house to her grandmother's house.\n";
        }
    }
    return 0;
}

:::

---

### [D - Weak Takahashi](https://atcoder.jp/contests/abc232/tasks/abc232_d)

撰寫者：小麥

BFS + DP，跟前面幾題有點像，但這題有可以整張圖被切成兩半，所以要用BFS。
還有BFS要記得設Visited，不然會TLE。

:::spoiler code

#include <bits/stdc++.h>

using namespace std;

// const int mod = 998244353;
int n, m;
vector<vector<int>> arr;
vector<vector<int>> dp;
vector<vector<bool>> visited;
queue<pair<int, int>> bfs;

signed main() 
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    cin >> n >> m;
    arr.resize(n + 1, vector<int>(m + 1));
    for (int i = 1; i <= n; i++)
    {
        string row;
        cin >> row;
        for (int j = 1; j <= m; j++)
        {
            if (row[j - 1] == '#')
            {
                arr[i][j] = 1;
            }
        }
    }

    dp.resize(n + 1, vector<int>(m + 1, 0));
    visited.resize(n + 1, vector<bool>(m + 1, 0));
    bfs.push({1, 1});
    while (bfs.size())
    {
        pair<int, int> f = bfs.front();
        bfs.pop();
        if (f.first != n && arr[f.first + 1][f.second] != 1)
        {
            if (!visited[f.first + 1][f.second])
            {
                bfs.push({f.first + 1, f.second});
                visited[f.first + 1][f.second] = true;
            }
        }
        if (f.second != m && arr[f.first][f.second + 1] != 1)
        {
            if (!visited[f.first][f.second + 1])
            {
                bfs.push({f.first, f.second + 1});
                visited[f.first][f.second + 1] = true;
            }
        }
        if (arr[f.first - 1][f.second] == 1)
        {
            dp[f.first][f.second] = dp[f.first][f.second - 1] + 1;
            continue;
        }
        if (arr[f.first][f.second - 1] == 1)
        {
            dp[f.first][f.second] = dp[f.first - 1][f.second] + 1;
            continue;
        }
        dp[f.first][f.second] = max(dp[f.first-1][f.second], dp[f.first][f.second-1]) + 1;
    }

    int result = 0;
    for (int i = 1; i <= n; i++)
    {
        for (int j = 1; j <= m; j++)
        {
            // cout << dp[i][j] << " ";
            result = max(result, dp[i][j]); 
        }
        // cout << "\n";
    }

    cout << result << '\n';

    return 0;
}

:::

---

### [zerojudge c001](https://zerojudge.tw/ShowProblem?problemid=c001)

撰寫者：Eason

LCS 裸題

:::spoiler code

#include<bits/stdc++.h>
#define ll long long
#define weakson ios::sync_with_stdio(0), cin.tie(0);
using namespace std;

int main(){
weakson;
string a, b;
while (cin >> a >> b){
    int a_len = a.size();
    int b_len = b.size();
    vector<vector<int> > dp(a_len + 1, vector<int>(b_len + 1, 0));

    for (int i = 1; i <= a_len; i++){
        for (int j = 1; j <= b_len; j++){
            if (a[i - 1] == b[j - 1]){
                dp[i][j] = dp[i - 1][j - 1] + 1;
            }
            else{
                dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]);
            }
        }
    }

    cout << dp[a_len][b_len] << '\n';
}
return 0;
}

:::

---

### [cses 1145](https://cses.fi/problemset/task/1145/)

撰寫者：Eason

LIS 裸題
這題要用 $O(n \log n)$ 的作法

:::spoiler code

#include<bits/stdc++.h>
#define ll long long
#define weakson ios::sync_with_stdio(0), cin.tie(0);
using namespace std;

int main(){
    weakson;

    int n;
    cin >> n;

    vector<int> v(n);

    for (int i = 0; i < n; i++) cin >> v[i];

    vector<int> dp;

    for (int i = 0; i < n; i++){
        auto p = lower_bound (dp.begin(), dp.end(), v[i]);
        if (p == dp.end()) dp.push_back (v[i]); // not found
        else dp[p - dp.begin()] = v[i];

        // cout << "dp : ";
        // for (int i : dp) cout << i << ' ';
        // cout << '\n';
    }

    cout << dp.size() << '\n';
}

:::