2020 競技程設教材 HackMD Book

2019 Week 9: Dynamic Programming (動態規劃)

第二週教材中分治法，提到了每個子問題都需互相獨立，就是每分割都將產生全新的問題
而本週介紹的動態規劃則適合在大部分的問題互相重疊

回憶一下第二週教材的那段話： "從邊界遞推地紀錄所有問題的解，且一個項用到前一項的最佳結果，就是動態規劃的精神。"

這裡給出正式的定義：
一個問題若能用 Dynamic Programming (以下簡稱 DP) 求解，其該問題含有以下三個性質：

• 最優子結構
  問題的最優解，是該子問題最優解的合併解。其子問題也具有同樣的特性
• 重複子問題
  有很多子問題可歸為同樣的問題
• 無後效性
  確定的子問題解，並不會受到其他決策影響(還在整個問題的求解過程中)

DP 不滿足第一週教材中提到的演算法三步驟，它僅是個方法

DP 入門

考慮一個問題

要買價值

$15$ 元的商品，有

$10$ 元、

$5$ 元、

$1$ 元硬幣，要求花最少的硬幣數。

日常生活中有個貪心策略是，每次用額面較大的硬幣去付
這樣就能使用較少的硬幣數，也就是

$\underset{―}{1}\cdot 10+\underset{―}{1}\cdot 5+\underset{―}{0}\cdot 1$

同樣

$15$ 元的商品，若現在硬幣額面只有

$11$ 元、

$5$ 元、

$1$ 元

顯然上述貪心策略就不是最佳策略了。

設

$f(x)$ 為價值

$x$ 元的商品所需要的最少硬幣數
若第一次：

• 選
  $11$ 元則可能
  $f(15)=f(4)+1$
• 選
  $5$ 元則可能
  $f(15)=f(10)+1$
• 選
  $1$ 元則可能
  $f(15)=f(14)+1$

將問題以

$f$ 形式化後：

$$f(x)=min\{f(x-11),f(x-5),f(x-1)\}+1$$

也就是說，求解

$f(x)$ 需要用到 3 個子問題的解：

$$f(x-11),f(x-5),f(x-1)$$

以及邊界：

$$f(0)=0$$

最優子結構

$f(x)$ 的定義為湊出

$x$ 元的最少硬幣數
最少即

$f(x)$ 的最優解，而

$f(x)$ 仰賴 3 個子問題的最優解

無後效性

若求出了

$f(4)=4$，則不管未來要求任何

$f(t)$ 的解都不會改變

$f(4)$ 的解

重複子問題

若求

$f(9)$ 則需要先求解

$f(8),f(4)$

$f(4)$ 在之前可能已經找到解了，這就是重複的子問題
也就是說無需再為

$f(9)$ 重新計算

$f(4)$

經典 DP 問題

有非常多實用的演算法是使用 DP 方法所設計的，
比起學習這些演算法的實作，更重要的是要學習如何應用 DP 去設計出演算法

Fibonacci 數

Fibonacci 數列由

$0,1$ 開始，之後的數為前兩項相加得來
也就是

$0,1,1,2,3,5,8,13,21,...$

求數列第

$n\in \mathbb{N}$ 項的數

考慮用遞迴寫：

int solve(int n) {
  if (n == 1 || n == 2) return 1;
  return solve(n-1) + solve(n-2);
}

每個子問題都將分為兩個子問題，複雜度為

$O(2^n)$

而實際上此演算法將同樣的子問題計算過兩次以上
例如在

$n=5$ 時，會重複計算 solve(3) 兩次:

記憶化 (memoization^[1])

也就是說，只要在每次解出子問題後將結果記錄，下一次遇到重複的子問題就無需計算
複雜度改進為

$O(n)$

• top-down

int solve(int n) {
  if (fib[n]) return fib[n];
  return fib[n] = solve(n-1) + solve(n-2);
}

由原問題開始遞歸逐步計算子問題的解
優點：不會計算太多子問題
缺點：呼叫函式的成本頗高

• bottom-up

fib[1] = fib[2] = 1;
for (int i = 3; i <= n; i++) fib[i] = fib[i-1] + fib[i-2];

由邊界(最小子問題)逐步計算到原問題的解
優點：若適當的設計迭代順序則能很好的壓縮空間
缺點：可能會多計算無用的子問題

練習：

CODEFORCES 327A Flipping Game
CODEFORCES 1033C Permutation Game
* CODEFORCES 1133E K Balanced Teams

---

在繼續往下讀前，先複習第四週教材中關於搜尋的術語

背包問題

給固定體積的背包，以及各種體積及價值不盡相同的物品
在背包容量不超過體積上限的前提，使總價值最大。

經典的背包問題有以下幾類:

• 無限背包問題：
  對每種物品，其個數是無限多個
• 01 背包問題：
  對每種物品，其個數是
  $1$ 個
• 多重背包問題：
  對每種物品，其個數是有限多個

先用一個比較生活化的例子來說，假設有一個古代的東方商人想沿著絲路走至西方販賣珍奇古物，但是他當然沒辦法將所有店內的商品帶去，所以為了最大化此趟旅程所能賺到的錢，他必須在他的大後背包內放入總價值最多的商品

對沒錯，他要用走的

假設他的大背包容量為

$8$ 公升，以下是一些他想帶去販售的商品:

Index	價值	體積
1	$10$ 克朗	$2$ L
2	$80$ 克朗	$3$ L
3	$110$ 克朗	$4$ L
4	$150$ 克朗	$5$ L
5	$200$ 克朗	$6$ L

以商品都能賣出去為前提，請問該怎麼帶才能最大化收益呢？

在進入正題前，讀者可以先思考一下這個看起來似乎蠻簡單的問題
要使得總價值最大不就是先算好各物品的 C/P 值，然後從最高的開始挑起嗎？
這樣做會發生什麼事？ 最佳解又是多少？

背包問題的術語約定：

• $P_i$ 代表第
  $i$ 件物品的價值
• $V_i$ 代表第
  $i$ 件物品的體積

01 背包問題

例如：

價值	體積
$70$ 克朗	$2$ L
$80$ 克朗	$4$ L
假設剩下 $4$ L 的體積，無限背包問題中會選兩個 $2$ L 的商品；
但在 01 背包問題中，只能選擇 $4$ L 的商品

先設計出狀態的定義，以及狀態轉移方程：
狀態

$S(i,n)$ 表示只考慮

$1$ 到

$i$ 項物品，背包體積為

$n$ 時的最大價值。
這個最大值，是下列兩項其中之一

• 包含第
  $i$ 個物品：
  $S(i-1,n-V_i)+P_i$
• 不包含第
  $i$ 個物品：
  $S(i-1,n)$

也就是狀態轉移方程：

$$S(i,n)=max(S(i-1,n-V_i)+P_i,S(i-1,n))$$
而當背包體積小於

$V_i$ 時，

$$S(i,n)=S(i-1,n)$$
以及邊界 (當沒有挑任何物品時)：

$$S(0,n)=0$$

假設有

$C$ 種物品，利用上述觀念來寫：

for (int n = 0; n <= maxn; n++) S[0][n] = 0;

for (int i = 1; i < C; i++)
  for (int n = 0; n <= maxn; n++) {
    if (n >= V[i])
      S[i][n] = max(S[i-1][n], S[i-1][n-V[i]] + P[i]);
    else
      S[i][n] = S[i-1][n];
  }

空間優化

狀態定義

$S(n)$ 代表目前背包體積為

$n$ 的最大價值
然後面對第

$i$ 個物品，考慮該不該拿，其中狀態轉移方程：

$$\mathrm{\forall }n.S(n)=max(S(n-V_i)+P_i)$$

for (int i = 1; i < C; i++)
  for (int n = maxn; n >= V[i]; n--)
    S[n] = max(S[n], S[n-V[i]] + P[i]);

這裡有個重點：

for (int n = maxn; n >= V[i]; n--)

此順序必須為從大到小，
舉個反例，若當

$S(n-V_i)$ 決定拿

$i$ 物品，

$S(n)$ 也決定拿

$i$ 物品
由於若

$S(n)=S(n-V_i)+P_i$，這樣

$S(n)$ 相當於拿了兩次

$i$ 物品，違反了 01 背包問題的前提。

這個優化叫做滾動陣列

範例 UVa OJ 10465 Homer Simpson：

辛普森先生吃 Krusty 漢堡需要

$m$ 時間，Apu’s Kwik-e-Mar 漢堡則需要

$n$ 時間

給定

$t$ 時間，辛普森先生不想浪費任何時間，無時無刻得一直吃漢堡，求辛普森先生在

$t$ 結束前能吃的最多漢堡數。
如果一定得浪費時間，辛普森先生可以喝啤酒(?)

要求輸出辛普森先生在時限內可以吃進最多的漢堡數，若可以喝啤酒，則需要再輸出浪費多少時間。

因為每種漢堡可以吃無限多個，但 01 背包問題限制每種只能選一次
也就是說，只要創造更多種漢堡就好！

對於原本的漢堡
創造出個數(價值)為

$2,3,..$，以及吃的時間(體積)為

$m\cdot 2,m\cdot 3,..$ 的多種漢堡(物品)

不過各位學過二進制都知道，只需要

$1,2,4,8,..$ 就可以做出任意正整數

int C = 1;

for (int i = 0; m * pow(2, i) <= t; i++) {
  V[C] = m * pow(2, i);
  P[C] = pow(2, i);
  C++;
}

for (int i = 0; n * pow(2, i) <= t; i++) {
  V[C] = n * pow(2, i);
  P[C] = pow(2, i);
  C++;
}

轉成背包問題的術語後，
定義狀態

$S(i,n)$ 表示只考慮

$1$ 到第

$i$ 種物品、背包體積

$n$ 且不浪費任何體積的最大價值
則狀態轉移方程：

$$S(i,n)=max(S(i-1,n),S(i-1,n-V_i)+P_i)$$
但當

$n$ 小於

$V_i$ 或

$S(i-1,n-V_i)$ 無解時，

$$S(i,n)=S(i-1,n)$$

$S(x,y)$ 無解的意思是： 背包體積為

$y$ 時，選

$x$ 物品一定得浪費體積！
而邊界為 (當背包體積為

$0$)：

$$\mathrm{\forall }i.S(i,0)=0$$

上段創造了

$C$ 種物品，利用上述觀念來寫：

for (int i = 1; i < C; i++)
  for (int n = 0; n <= t; n++)
    S[i][n] = (n==0)? 0 : -1;

for (int i = 1; i < C; i++)
  for (int n = 0; n <= t; n++) {
    if (n >= V[i] && S[i-1][n-V[i]] != -1)
      S[i][n] = max(S[i-1][n], S[i-1][n-V[i]] + P[i]);
    else
      S[i][n] = S[i-1][n];
  }

其中 -1 代表無解的狀態。

接著看浪費多少體積：

for (int n = t; n >= 0; n--) if (S[C-1][n]) {
  printf("%d", S[C-1][n]);
  if (n < t) printf(" %d", t-n);
  putchar('\n');
  break;
}

練習：

UVa OJ 624 CD
UVa OJ 10130 SuperSale
UVa OJ 10819 Trouble of 13-Dots

無限背包問題

首先設計出此問題的狀態定義：

$S(n)$ 狀態表示在背包體積為

$n$ 時的最大價值

最好盡可能簡單直覺

假設背包體積為

$n-V_i$，則加入第

$i$ 個物品後，總價值為：

$$S(n-V_i)+P_i$$
所以，狀態轉移方程為：

$$S(n)=\underset{i}{max}(S(n-V_i)+P_i)$$

對於解

$S(n)$，每次討論

$i$ 物品時，子問題都需先得到最優解
也就是

$S(n-V_i)$ 要先得到最優解，才能求解

$S(n)$

以及邊界 (還未挑任何物品)：

$$\mathrm{\forall }n.S(n)=0$$

假設有

$C$ 種物品，利用上述觀念來寫：

memset(S, 0, sizeof S); // 還未挑任何東西的初始邊界

for (int i = 1; i <= C; i++)
  for (int n = V[i]; n <= maxn; n++)
    S[n] = max(S[n], S[n-V[i]] + P[i]);

與 01 背包的空間優化版本相反，這裡

$n$ 順序該從小到大

理解這段程式碼得先看懂 01 背包的空間優化

範例 UVa OJ 10465 Homer Simpson：

與 01 背包問題的範例一樣：

memset(S, -1, sizeof S);
S[0] = 0;

for (int j = m; j <= t; j++) if (S[j-m] != -1) S[j] = max(S[j], S[j-m] + 1);
for (int j = n; j <= t; j++) if (S[j-n] != -1) S[j] = max(S[j], S[j-n] + 1);

接著看浪費多少時間：

for (int i = t; i >= 0; i--) if (S[i]) {
  printf("%d", S[i]);
  if (i < t) printf(" %d", t-i);
  putchar('\n');
  break;
}

練習：

UVa OJ 10980 Lowest Price in Town
POJ 2063 Investment

Longest Increasing Subsequence (LIS)

Longest Increasing Subsequence 中譯為 最長遞增子序列

在給定

$N$ 長度序列

$a$，找到一個子序列，為嚴格遞增且長度最長。

例如

$a=(\mathbf{\text{1}},4,\mathbf{\text{2}},3,8,\mathbf{\text{3}},\mathbf{\text{4}},1,\mathbf{\text{9}})$
則 LIS 為

$(1,2,3,4,9)$ 或

$(1,2,3,8,9)$

仔細考慮，若某數字在某遞增子序列後出現，並且它比此序列的末項還大，那麼加入它就能形成更長的遞增子序列！
不過在那之前，這個遞增序列是如何求得的？

通過上述，定義狀態

$S(n)$ 為以第

$n$ 個數為結尾的 LIS 長度，

意思是在

$a_1,a_2,..,a_n$ 之間找個一定要包含

$a_n$ 的 LIS

且狀態轉移方程為，對於所有

$i<n$ 且

$a_n>a_i$：

$$S(n)=max(S(i)+1)$$

也就是找出所有在

$a_n$ 之前的遞增子序列，選出最長的

若找不到

$a_n$ 之前的遞增子序列，邊界為：

$$S(n)=1$$

for (int n = 1; n <= N; n++) {
  S[n] = 1;
  f[n] = n;
}

for (int n = 2; n <= N; n++) // N 為 a 的總長度
  for (int i = 1; i <= n; i++)
    if (a[n] > a[i] && S[n] < S[i] + 1) {
      S[n] = S[i] + 1;
      f[n] = i; // 紀錄遞增子序列
    }

複雜度為

$O(N^2)$

其中 f[n] 代表遞增子序列中 a[f[n]] 下個接 a[n]
例如

$a=(\mathbf{\text{1}},4,\mathbf{\text{2}},\mathbf{\text{3}},\mathbf{\text{8}},3,4,1,\mathbf{\text{9}})$
得出

$f=(\mathbf{\text{1}},1,\mathbf{\text{1}},\mathbf{\text{3}},\mathbf{\text{4}},3,4,8,\mathbf{\text{5}})$

所以利用 f 就能將其中一個 LIS 輸出！

$a_9=\mathbf{\text{9}}$ 為末項的 LIS 為例：

$f_9=5\to a_5=\mathbf{\text{8}}$

$f_5=4\to a_4=\mathbf{\text{3}}$

$f_4=3\to a_3=\mathbf{\text{2}}$

$f_3=1\to a_1=\mathbf{\text{1}}$

$f_1=1$

$f_i=i$ 表示

$a_i$ 為欲輸出的 LIS 首項

另一種狀態定義

直覺的，當前 LIS 末項數字越小，那麼越有可能使得 LIS 繼續變長

根據這樣的貪心策略，
定義狀態

$S(i,l)$ 為

$(a_1,a_2,..,a_i)$ 長度

$l$ 的 LIS 最小末項

狀態轉移方程：

$$S(i,l)=\{\begin{array}{ll}min(a_i,S(i-1,l))& \text{if }{a}_i>S(i-1,l-1)\\ S(i-1,l)& \text{otherwise}\end{array}$$

$S(i,l)$ 有可能無解， 或許找不到長度為

$l$ 的 LIS

邊界：

$$S(1,1)=a_1$$

for (int l = 1; l <= N; l++) S[1][l] = INF;
S[1][1] = a[1];
int t = 1; // LIS 初始長度

for (int i = 2; i <= N; i++) {
  for (int l = 1; l <= t; l++) S[i][l] = min(a[i], S[i-1][l]);
  if (a[i] > S[i-1][t]) S[i][++t] = a[i];
}

這裡尚未用 f 去紀錄 LIS

由於狀態的解是

$i$ 從小到大遞推得到，可用滾動陣列壓縮一個維度

同學自行研究，這很簡單的

且這裡

$S$ 是單調的，於是每次將

$a_i$ 更新至序列中，就使用二分搜！

for (int i = 1; i <= N; i++) S[i] = INF, f[i] = i;
S[1] = a[1];
int t = 1; // LIS 初始長度

for (int i = 1; i <= N; i++) {
  int l = lower_bound(S+1, S+t+1, a[i]) - S;
  if (l == t+1) t++;

  S[l] = a[i];
  p[l] = i;
  f[i] = (l==1)? i : p[l-1];
}

其中 p[l] 為 S[l] 在原本

$a$ 序列中的位置
且由於長度是從

$1$ 開始的，所以左邊界為

$1$，右邊界為

$t$
複雜度為

$O(N{\log }_{2}N)$

練習：

UVa OJ 10131 Is Bigger Smarter?
UVa OJ 10534 Wavio Sequence
UVa OJ 437 The Tower of Babylon
CODEFORCES 1257E The Contest

Longest Common Subsequence (LCS)

Longest Common Subsequence 中譯為 最長公共子序列

在兩個序列

$A,B$ 中找到一個相同(公共)且最長的子序列。

例如：

$A=(\mathbf{\text{1}},4,2,3,8,\mathbf{\text{3}},\mathbf{\text{4}},\mathbf{\text{1}},\mathbf{\text{9}})$

$B=(0,\mathbf{\text{1}},\mathbf{\text{3}},7,7,\mathbf{\text{4}},\mathbf{\text{1}},9,\mathbf{\text{9}})$
則 LCS 為

$(1,3,4,1,9)$

與 LIS 類似，
若某數字在某公共子序列後出現，並且它為兩序列的公共數字，那麼加入它就能形成更長的公共子序列！
不過在那之前，這個公共序列是如何求得的？

通過上述，定義狀態

$S(n,m)$ 為以

$A_n$ 以及

$B_m$ 為結尾的 LCS 長度，
則狀態轉移方程為：

$$S(n,m)=\{\begin{array}{ll}S(n-1,m-1)+\mathbf{\text{1}}& \text{if }{A}_n=B_m\\ max(S(n-1,m),S(n,m-1))& \text{if }{A}_n\ne B_m\end{array}$$

也就是找出在

$B_m,A_n$ 之前的公共子序列，選出最長的！

假設

$A$ 序列長度為

$\text{AN}$，

$B$ 序列長度為

$\text{BN}$，利用上述定義：

for (int n = 1; n <= AN; n++)
  for (int m = 1; m <= BN; m++) {
    if (A[n] == B[m])
      S[n][m] = S[n-1][m-1] + 1;
    if (A[n] != B[m])
      S[n][m] = max(S[n-1][m], S[n][m-1]);
  }

一樣的，假設

$A,B$ 為

$$\begin{gathered} B=(0,\mathbf{\text{1}},\mathbf{\text{3}},7,7,\mathbf{\text{4}},\mathbf{\text{1}},9,\mathbf{\text{9}}) \\ A=(\mathbf{\text{1}},4,2,3,8,\mathbf{\text{3}},\mathbf{\text{4}},\mathbf{\text{1}},\mathbf{\text{9}}) \end{gathered}$$
則輸出

$S$ 會長這樣 (第一個 row 為

$B$， 第一個 column 為

$A$)：

	0	1	3	7	7	4	1	9	9
1	0	1	1	1	1	1	1	1	1
4	0	1	1	1	1	2	2	2	2
2	0	1	1	1	1	2	2	2	2
3	0	1	2	2	2	2	2	2	2
8	0	1	2	2	2	2	2	2	2
3	0	1	2	2	2	2	2	2	2
4	0	1	2	2	2	3	3	3	3
1	0	1	2	2	2	3	4	4	4
9	0	1	2	2	2	3	4	5	5
標上紫色的為 LCS 中的數，而粉紅則為此時的長度
也就是說，只要順著狀態轉移方程以及 $S$ 上的數，就能找到 LCS

int n = AN, m = BN;

while(n && m) {
  if (S[n][m] != max(S[n-1][m], S[n][m-1])) {
    LCS.push_back(A[n]);
    n--; m--;
  }
  else if (S[n][m] == S[n-1][m]) n--;
  else if (S[n][m] == S[n][m-1]) m--;
}

reverse(LCS.begin(), LCS.end());

練習：

UVa OJ 10405 Longest Common Subsequence
UVa OJ 10066 The Twin Towers
UVa OJ 10192 Vacation
UVa OJ 531 Compromise

Greedy method (貪心法)

貪心法是 DP 的一種特例

回憶一下第二週教材的那段話：
"每次做一個在當下看起來最佳的決策，進而漸漸求出全局最佳解"

一旦證明問題能被貪心法解決，通常貪心法是問題的最佳策略，因為放棄搜索所有解答空間，效率會提高不少。

通常觀察出一個問題是否有最優子結構時
就可假設看看：下某個決策能漸漸朝全局最佳解的方向走
接著證明每次做這個決策一定不會更差

證明(或直覺?)很重要，有些看似美好的假設，不見得能求得問題的解

範例 TIOJ 1072 A.誰先晚餐：

直覺是先讓吃最慢的人先上菜

比較看看，若

$a$ 和

$b$ 的吃速

$E_a<E_b$，煮菜速度

$C_a,C_b$

• 先讓
  $a$ 上，總時間：
  $C_a+max(E_a,C_b+E_b)=C_a+C_b+E_b$
• 先讓
  $b$ 上，總時間：
  $C_b+max(E_b,C_a+E_a)$
• 不管
  $a,b$ 誰先上，其他人用餐時間都不會受到影響 (自行證明吧)

將總時間的

$C_b$ 消去後發現

$C_a+E_b$ 大於

$max(E_b,C_a+E_a）$，
所以先讓

$b$ (吃較慢)上菜會比較快！

#include<bits/stdc++.h>
using namespace std;

int const maxn = 1e4 + 10;

int N, C[maxn], E[maxn];

int main()
{
  while(scanf("%d", &N) && N) {
    vector<int> idx;
    for(int i = 0; i < N; i++) {
      scanf("%d%d", &C[i], &E[i]);
      idx.push_back(i);
    }

    sort(idx.begin(), idx.end(), [&](int x, int y) { return E[x] > E[y]; });

    int cook = 0, time = 0;
    for(int i: idx) {
      cook += C[i];
      time = max(time, cook + E[i]);
    }

    printf("%d\n", time);
  }

  return 0;
}

範例 CODEFORCES 1076C Make It Equal：

是第一場比賽的題目呢

模擬切格子的步驟就行了
從最高的地方 (maxh) 一路一層層往最低處 (1) 看

for(int i = maxh; i >= 1; i--) {
  :
  .
}

對於每一層，收集該層的格子們

$s$，收集完存到累計的 sum 中

sum += s;

但是當該層的格子加進 sum 中會超過

$k$ 時，就不能再收集了
此時這個位置就是要 slice 的地方

if(sum + s > k) slice++, sum = 0;

而當

$s$ 等於

$n$ 時，也就是所有 tower 都一樣高了，就可以結束了

if(s == n) {
  if(sum) slice++;
  break;
}

這裡特別注意 sum 如果還有東西，表示結束前還要切一刀 (slice)

在以上步驟之前，我們還得問，如何知道某層的

$s$ 為何？

for(int i = 0; i < n; i++) scanf("%d", &h), s[h]++;
for(int i = maxh; i >= 1; i--) s[i-1] += s[i];

以下完整解題程式碼：

#include<bits/stdc++.h>
using namespace std;

int const maxh = 2e5 + 10;

int n, k, s[maxh];

int main()
{
  scanf("%d%d", &n, &k);

  int h;
  for(int i = 0; i < n; i++) scanf("%d", &h), s[h]++;

  for(int i = maxh-1; i >= 1; i--) s[i-1] += s[i];

  int sum = 0, ans = 0;
  for(int i = maxh-1; i >= 1; i--) {
    if(s[i] == n) {
      if(sum) ans++;
      break;
    }

    if(sum + s[i] > k) ans++, sum = 0;

    sum += s[i];
  }

  printf("%d\n", ans);

  return 0;
}

練習:

CODEFORCES 1140D Minimum Triangulation
ZEROJUDGE d652 貪婪之糊
ZEROJUDGE d133 00357 - Let Me Count The Ways
TIOJ 1861 蘿莉切割問題
TIOJ 1636 錢包的路
STEP5 0021 背包問題

---

1. 這單字並沒有拼錯。 ↩︎