###### tags: `Weekly Contest`
# Weekly Contest 350

## [2739. Total Distance Traveled](https://leetcode.com/problems/total-distance-traveled/)(<font color=#00B8A3>Easy</font>)

限制 :

<ul>
<li><code>1 &lt;= mainTank, additionalTank &lt;= 100</code></li>
</ul>

### Solution
這題算是常見的題目，感覺不用講應該也會。(優化後的我倒是不會🥵)
最主要的點是要看的懂，它的主燃料箱每五公升，會從副燃料箱中抽一公升過去。
#### 時間複雜度: $O(n)$

#### 空間複雜度: $O(1)$

程式碼:

class Solution {
public:
    int distanceTraveled(int mainTank, int additionalTank) {
        int result  = 0;
        while(mainTank >= 5)
        {
            mainTank -= 5;
            result+=50;
            if(additionalTank > 0)
            {
                additionalTank -=1;
                mainTank+=1;
            }
        }
        result+= mainTank*10;
        return result;
    }
};
// 我還是不知道這個的時間複雜度是多少

## [2740. Find the Value of the Partition](https://leetcode.com/problems/find-the-value-of-the-partition/)(<font color=#FFC011>Medium</font>)

限制 :

<ul>
<li><code>2 &lt;= nums.length &lt;= 10⁵</code></li>
<li><code>1 &lt;= nums[i] &lt;= 10⁹</code></li>
</ul>

### Solution

他要的是某兩個陣列當中分別最大的值與最小的值，然後相減出來的值要最小。
我把他理解成，有序陣列當中相鄰相間的值最小的，其原因在於我可以把比較小的值當作某個陣列的最大值，比較大的值當作另外一組陣列的最小值，相減得到的值就是所要的答案。
#### 時間複雜度: $O(n*logn)$

#### 空間複雜度: $O(1)$

程式碼:

class Solution {
public:
    int findValueOfPartition(vector<int>& nums) {
        sort(nums.begin(),nums.end());

        int result = INT_MAX;

        for(int i=0;i< nums.size()-1;i++)
        {
            result = min(result, nums[i+1]- nums[i]);
        }

        return result;
    }
};

## [2741. Special Permutations](https://leetcode.com/problems/special-permutations/)(<font color=#FFC011>Medium</font>)

限制 :

<ul>
<li><code>2 &lt;= nums.length &lt;= 14</code></li>
<li><code>1 &lt;= nums[i] &lt;= 10⁹</code></li>
</ul>

### Solution
參考[這篇](https://leetcode.com/problems/special-permutations/solutions/3650431/easy-bitmask-dp-with-explanation-of-overlapping-top-down-c-beats-100-100/)。

因為所有排列的數量有 $14!$，所以暴力列舉是行不通的。這時候就需要使用到 dynamic programming 的思想來解決。

首先因為 $n<=14$，所以我們可以使用 **bit mask** 來記錄數字被選擇的狀態。假設題目給定的數列是 $[3, 6, 8, 9]$，那我們會選擇用 $4$ 個bit去表示該數列的狀態，舉例來說像是 $1101$ 就代表 $[3, 6, 9]$、$0101$ 代表 $[6, 9]$。

令 $dp[mask][idx]$ 為從 $mask$ 這個狀態下，且數列的最後一個元素是 $nums[idx]$ 開始，最終能組合成的 *Special Permutations* 總共有幾種。

從這個定義來看，base case 是當 $mask$ 全為 1 的時候，代表所有數字都已經被選擇了且整個數列是一個 *Special Permutations*，這種情況應該要回傳 1。

那對於某一個狀態我們要怎麼遞進到下一個狀態呢?
只需要 check 當前mask為 0 的數是否符合 *Special Permutations* 的條件。當前狀態的解就等於所有符合條件的下一個狀態的解的加總。也就是:
$$
\forall i \ satisfy \
\begin{cases}
mask[i]=0\\
nums[idx]\ \%\ nums[i]=0\ or\ nums[i]\ \%\ nums[idx]=0 \\
\end{cases} \\
next\_mask_i := mask\ |\ 2^i \\
dp[mask][idx] := \sum_i dp[next\_mask_i][i]\\
$$
以此來遞迴求解。
那解答就是 $dp[100...000][0]+dp[010...000][1]+dp[001...000][2]+...+dp[000...001][n-1]$。
也可以說解答是 $dp[000...000][any]$，但因為這個狀態不是合法的狀態，畢竟沒有選任何數怎麼可能會有最後被選的數。所以只能取只有一個 1 的合法狀態來計算結果。
#### 時間複雜度: $O(n*2^n)$

#### 空間複雜度: $O(n*2^n)$

程式碼:

class Solution {
public:
    const int MOD = 1e9+7;
    int n;
    int dp[1<<14][14];
    int helper(int prev, int mask, vector<int>& nums){
        if(prev != -1 && dp[mask][prev] != -1)
            return dp[mask][prev];
        if(mask == (1<<n)-1)
            return 1;

        int total = 0;
        for(int j=0;j<n;j++){
            if(mask&(1<<j))
                continue;
            if(prev == -1 || nums[prev] % nums[j] == 0 || nums[j] % nums[prev] == 0)
                total = (total + helper(j, mask | (1<<j), nums))%MOD;
        }
        if(prev != -1)
            return dp[mask][prev] = total;
        return total;
    }
    int specialPerm(vector<int>& nums) {
        n = nums.size();
        memset(dp, -1, sizeof dp);

        return helper(-1, 0, nums);
    }
};

## [2742. Painting the Walls](https://leetcode.com/problems/painting-the-walls/)(<font color=#FF375F>Hard</font>)

限制 :

<ul>
<li><code>1 &lt;= cost.length &lt;= 500</code></li>
<li><code>cost.length == time.length</code></li>
<li><code>1 &lt;= cost[i] &lt;= 10⁶</code></li>
<li><code>1 &lt;= time[i] &lt;= 500</code></li>
</ul>

### Solution
跟背包問題類似，從最大化收益變成最小化成本，背包重量變成牆壁數量。

我們可以把 free printer 視為是 paid printer 的 bonus。假設我們用 paid printer 塗了第 $i$ 道牆，那等於我們花了 $cost[i]$ 塗了 $1+time[i]$ 道牆，前面的 1 是 paid printer 塗的，後面的 $time[i]$ 是 free printer 塗的。

由此可以導出 dp 式，令 $dp[j]$ 是塗 $j$ 道牆所需要的最小成本:
$$
\forall i \in [0, n-1]\\
dp[j] = min(dp[j], dp[max(0, j-time[i]-1)]+cost[i])
$$

$dp[n]$ 即是所求。
#### 時間複雜度: $O(n^2)$

#### 空間複雜度: $O(n)$

程式碼:

class Solution {
public:
    int paintWalls(vector<int>& cost, vector<int>& time) {
        int dp[505], n = cost.size();
        for(int i=0;i<=n;i++)
            dp[i] = 1e9;
        dp[0] = 0;
        for(int i=0;i<n;i++){
            for(int j=n;j>0;j--){
                dp[j] = min(dp[j], dp[max(0, j-time[i]-1)]+cost[i]);
            }
        }
        return dp[n];
    }
};