Educational DP Contest

A - Frog 1

你有 N 個平台。平台編號為 1, 2, …, N。對於每個 i (1 ≤ i ≤ N)，平台 i 的高度是 h_i。

最初，一隻青蛙在平台 1 上。

青蛙重複以下動作，試圖到達平台 N：

  • 當青蛙在平台 i 上時，它跳到平台 i + 1 或 i + 2。
  • 當跳到平台 j 時，它支付成本 |h_i - h_j|。

求青蛙到達平台 N 所需支付的最小總成本。

n = int(input())
h = list(map(int, input().split()))
dp = [0] * n
dp[1] = abs(h[1] - h[0])
for i in range(2, n):
  dp[i] = min(dp[i-1] + abs(h[i] - h[i-1]), dp[i-2] + abs(h[i] - h[i-2]))
print(dp[-1])

B - Frog 2

有 N 個立足點。立足點的編號是 1, 2, …, N。對每個 i (1 ≤ i ≤ N)，立足點 i 的高度是 h_i。

最初，青蛙在立足點 1。青蛙重複以下行動若干次，試圖到達立足點 N。當青蛙在立足點 i 時，可以跳到立足點 i + 1, i + 2, …, i + K 中的任意一個。此時，如果跳到的立足點是 j，則需要支付成本 |h_i - h_j|。

求青蛙到達立足點 N 之前需要支付的總成本的最小值。

n, k = map(int, input().split())
h = list(map(int, input().split()))
dp = [0] * n
for i in range(1, n):
  dp[i] = min(dp[i-j] + abs(h[i] - h[i-j]) for j in range(1, min(i+1, k+1)))
print(dp[-1])

C - Vacation

明日太郎君的暑假就要開始了。

太郎君決定要規劃他的暑假。暑假總共有 N 天。

對每一個 i (1 ≤ i ≤ N)，在第 i 天，太郎君可以選擇以下其中一項活動：

  • A：去海邊游泳。獲得幸福度 a_i。
  • B：去山上抓蟲。獲得幸福度 b_i。
  • C：在家裡寫作業。獲得幸福度 c_i。

太郎君很容易感到厭倦，所以他不能連續兩天或更多天做相同的活動。

請找出太郎君能獲得的最大總幸福度。

D - Knapsack 1

有 N 個物品。物品編號為 1, 2, …, N。 對於每個 i (1 ≤ i ≤ N)，物品 i 的重量為 wᵢ，價值為 vᵢ。 太郎君要從 N 個物品中選擇一些，放入背包帶走。 背包的容量為 W，帶走的物品的重量總和必須 ≤ W。 請找出太郎君帶走的物品的價值總和的最大值。

限制：

  • 所有輸入皆為整數。
  • 1 ≤ N ≤ 100
  • 1 ≤ W ≤ 10⁵
  • 1 ≤ wᵢ ≤ W
  • 1 ≤ vᵢ ≤ 10⁹

E - Knapsack 2

限制：

  • 所有輸入都是整數。
  • 1 ≤ N ≤ 100
  • 1 ≤ W ≤ 10⁹
  • 1 ≤ wᵢ ≤ W
  • 1 ≤ vᵢ ≤ 10³

F - LCS

給定字串 s 和 t。請找出 s 的子序列，同時也是 t 的子序列的最長字串之一。

註解

字串 x 的子序列是指從 x 中移除 0 個或更多字元後，將剩餘字元按原始順序連接起來所形成的字串。

限制

  • s 和 t 都是由小寫英文字母組成的字串。
  • 1 ≤ |s|, |t| ≤ 3000

G - Longest Path

問題：

給定一個有向圖G，包含N個頂點和M條邊。頂點的編號為1, 2, …, N。對於每個 i (1 ≤ i ≤ M)，第 i 條有向邊從頂點 x_i 指向頂點 y_i。圖G不包含有向環。

求G中，最長有向路徑的長度。

有向路徑的長度定義為路徑中包含的邊的數量。

限制：

  • 所有輸入皆為整數。
  • 2 ≤ N ≤ 10^5
  • 1 ≤ M ≤ 10^5
  • 1 ≤ x_i, y_i ≤ N
  • 所有的 (x_i, y_i) 對都是不同的。
  • 圖G不包含有向環。

H - Grid 1

給定一個 H 行 W 列的網格。 用 (i, j) 表示從上到下第 i 行，從左到右第 j 列的方格。 對於每個 i, j (1 ≤ i ≤ H, 1 ≤ j ≤ W)，方格 (i, j) 的資訊由字元 a_{i, j} 給出。如果 a_{i, j} 是 .，則方格 (i, j) 是空方格；如果 a_{i, j} 是 #，則方格 (i, j) 是牆方格。 保證方格 (1, 1) 和 (H, W) 是空方格。

太郎君從方格 (1, 1) 出發，通過重複向右或向下移動到相鄰的空方格，來嘗試到達方格 (H, W)。 從方格 (1, 1) 到 (H, W) 的太郎君的路徑有多少種？ 由於答案可能非常大，請計算對 10^9 + 7 取模的結果。

條件：

  • H 和 W 是整數。
  • 2 ≤ H, W ≤ 1000
  • a_{i, j} 是 . 或 #。
  • 方格 (1, 1) 和 (H, W) 是空方格。

I - Coins

題目敘述

給定一個正奇數 N。有 N 枚硬幣，編號為 1, 2, …, N。對於每個 i (1 ≤ i ≤ N)，當你拋擲硬幣 i 時，正面朝上的機率是 pᵢ，反面朝上的機率是 1 - pᵢ。太郎將所有 N 枚硬幣都拋擲了。請求出正面朝上的硬幣數量多於反面朝上的硬幣數量的機率。

條件

  • N 是一個奇數。
  • 1 ≤ N ≤ 2999
  • pᵢ 是一個實數，最多有兩位小數。
  • 0 < pᵢ < 1

J - Sushi

你有 N 個盤子。盤子上分別標記著 1, 2, …, N。 最初，對於每個 i (1 ≤ i ≤ N)，盤子 i 上有 aᵢ (1 ≤ aᵢ ≤ 3) 個壽司。 直到所有壽司都被吃光，太郎都會重複進行以下操作：

  1. 擲一個骰子，骰子的每個面出現的概率相等，骰子的點數為 1, 2, …, N。
  2. 假設骰子的點數為 i。如果盤子 i 上有壽司，則吃掉盤子 i 上的一個壽司。
  3. 如果盤子 i 上沒有壽司，則什麼也不做。

請求出所有壽司都被吃光之前，操作次數的期望值。

K - Stones

給定一個由 N 個正整數組成的集合 A = { a₁，a₂，…，aN }。

太郎君和次郎君玩一個遊戲。

首先，準備一堆由 K 個石頭組成的石堆。

兩人輪流進行以下操作。

先手是太郎君。從集合 A 中選擇一個元素 x，從石堆中恰好拿走 x 個石頭。

無法再進行操作的人輸。

假設兩人都採取最佳策略，判斷誰會獲勝。

L - Deque

太郎君和次郎君進行一個遊戲。

最初，給定一個數列 a = (a₁，a₂，…，aₙ)。 太郎君和次郎君輪流進行操作，直到數列 a 變為空。

每次操作，玩家可以從數列 a 的開頭或結尾移除一個元素。 移除的元素值為 x，進行操作的玩家得到 x 分。

遊戲結束時，太郎君的總得分為 X，次郎君的總得分為 Y。

太郎君的目標是最大化 X - Y，而次郎君的目標是最小化 X - Y。

假設兩人都採取最佳策略，請求出 X - Y 的值。

條件

  • 所有輸入皆為整數。
  • 1 ≤ N ≤ 3000
  • 1 ≤ aᵢ ≤ 10⁹

M - Candies

有 N 個孩子。孩子的編號是 1, 2, …, N。他們要分 K 個糖果。

對於每個 i (1 ≤ i ≤ N)，孩子 i 得到的糖果數量必須是 0 以上且不超過 aᵢ。

而且，糖果不能剩下。

有多少種孩子們分配糖果的方法？答案對 10⁹ + 7 取模。

如果存在一個孩子，他/她得到的糖果數量不同，則認為兩種方法是不同的。

限制

所有輸入都是整數。

1 ≤ N ≤ 100

0 ≤ K ≤ 10⁵

0 ≤ aᵢ ≤ K

N - Slimes

有 N 隻史萊姆排成一列。 最初，從左邊數起的第 i 隻史萊姆的大小是 a_i。 太郎想把所有史萊姆合併成一隻。 在史萊姆變成一隻之前，太郎會重複以下操作：

選擇左右相鄰的兩隻史萊姆，將它們合併成一隻新的史萊姆。 當合併前兩隻史萊姆的大小分別為 x 和 y 時，合併後史萊姆的大小為 x + y。 此時，太郎需要支付 x + y 的成本。 史萊姆的位置關係在合併前後保持不變。

請找出太郎需要支付的成本總和的最小值。

限制：

所有輸入都是整數。 2 ≤ N ≤ 400 1 ≤ a_i ≤ 10^9

O - Matching

有 N 個男性和 N 個女性。男性編號為 1, 2, …, N，女性也編號為 1, 2, …, N。對於每對 i, j (1 ≤ i, j ≤ N)，用一個整數 a_{i, j} 來表示男性 i 和女性 j 的匹配程度。如果 a_{i, j} = 1，表示男性 i 和女性 j 相性良好，如果 a_{i, j} = 0，表示相性不好。

太郎君希望找到所有相性良好的男女配對，使得形成 N 對。

條件：

  • 每個男性和每個女性都必須恰好屬於一個配對。
  • 你需要計算有多少種不同的方式可以形成 N 對配對。
  • 答案對 10^9 + 7 取模。
  • 1 ≤ N ≤ 21
  • a_{i, j} 的值只能是 0 或 1。

P - Independent Set

問題：

給定一個有 N 個頂點的樹。 頂點編號為 1, 2, …, N。 對於每個 i (1 ≤ i ≤ N - 1)，第 i 條邊連接頂點 xi 和 yi。 太郎君決定將每個頂點塗成白色或黑色。 但是，相鄰的頂點不能同時塗成黑色。 請問頂點的顏色組合有多少種？ 請對 10^9 + 7 取餘數。

條件：

  • 所有輸入都是整數。
  • 1 ≤ N ≤ 10^5
  • 1 ≤ xi, yi ≤ N
  • 給定的圖是一個樹。

Q - Flowers

有 N 朵花排成一列。

對於每個 i (1 ≤ i ≤ N)，從左邊數來的第 i 朵花的高度是 h_i，美麗值是 a_i。

此外，h_1, h_2, …, h_N 彼此互不相同。

太郎想移除一些花，使得以下條件成立：

  • 剩餘的花從左到右看，高度是單調遞增的。

請求出剩餘的花的美麗值總和的最大值。

限制

  • 所有的輸入都是整數。
  • 1 ≤ N ≤ 2 × 10^5
  • 1 ≤ h_i ≤ N
  • h_1, h_2, …, h_N 彼此互不相同。
  • 1 ≤ a_i ≤ 10^9

R - Walk

給定一個有 N 個頂點的簡單有向圖 G。 頂點編號為 1, 2, …, N。 對於每個 i, j (1 ≤ i, j ≤ N)，由整數 a_{i, j} 給出從頂點 i 到 j 的有向邊是否存在。 如果 a_{i, j} = 1，則存在從頂點 i 到 j 的有向邊；如果 a_{i, j} = 0，則不存在。

請問 G 中有多少個長度為 K 的有向路徑？ 求出答案模 10^9 + 7 的結果。

允許有向路徑多次經過相同的邊。

限制：

輸入的所有值都是整數。 1 ≤ N ≤ 50 1 ≤ K ≤ 10^{18} a_{i, j} 是 0 或 1。 a_{i, i} = 0

S - Digit Sum

給定一個正整數 K 和一個正整數 D。請問有多少個介於 1 到 K 之間（包含 1 和 K）的整數，其十進位表示中所有數字的總和是 D 的倍數？ 答案對 10^9 + 7 取模。

限制

  • 所有輸入都是整數。
  • 1 ≤ K < 10^10000
  • 1 ≤ D ≤ 100

T - Permutation

給定一個正整數 N。

給定一個長度為 N - 1 的字符串 s，由 “<” 和 “>” 組成。

尋找有多少個 (1, 2, …, N) 的排列 (p_1, p_2, …, p_N) 滿足以下條件？ 輸出答案模 10^9 + 7 的結果。

對於每個 i (1 ≤ i ≤ N - 1)，如果 s 的第 i 個字符是 “<"，則 p_i < p_{i + 1}；如果 s 的第 i 個字符是 “>"，則 p_i > p_{i + 1}。

約束

  • N 是一個整數。
  • 2 ≤ N ≤ 3000
  • s 是一個長度為 N - 1 的字符串。
  • s 僅由 “<” 和 “>” 組成。

U - Grouping

有 N 隻兔子。

兔子們的編號是 1, 2, …, N。

對於每對 i, j (1 ≤ i, j ≤ N)，兔子 i 和 j 的相容性由整數 a_{i, j} 給定。

對於每個 i (1 ≤ i ≤ N) , a_{i, i} = 0，並且對於每個 i, j (1 ≤ i, j ≤ N), a_{i, j} = a_{j, i}。

太郎君想將這 N 隻兔子分成幾個群組。

此時，每隻兔子必須恰好屬於一個群組。

作為分組的結果，對於每對 i, j (1 ≤ i < j ≤ N)，如果兔子 i 和 j 屬於同一個群組，太郎君會得到 a_{i, j} 分。

求太郎君總得分的最大值。

限制

所有輸入都是整數。 1 ≤ N ≤ 16 |a_{i, j}| ≤ 10^9 a_{i, i} = 0 a_{i, j} = a_{j, i}

V - Subtree

題目描述

給定一個有 N 個節點的樹。 節點編號從 1 到 N。 對於每個 i ( 1 ≤ i ≤ N - 1 )，第 i 條邊連接節點 x_i 和 y_i。 太郎決定將每個節點塗成白色或黑色。 在這個情況下，所有黑色的節點之間，都能只通過黑色的節點到達彼此。 給定正整數 M。 對於每個 v ( 1 ≤ v ≤ N )，回答以下問題： 有多少種節點塗色的方法，使得節點 v 是黑色的？ 輸出結果對 M 取模。

條件

  • 所有輸入都是整數。
  • 1 ≤ N ≤ 10^5
  • 2 ≤ M ≤ 10^9
  • 1 ≤ x_i, y_i ≤ N
  • 給定的圖是一個樹。

W - Intervals

考慮一個長度為 N 的由 0 和 1 構成的字符串。

這個字符串的得分計算如下： 對於每個 i (1 ≤ i ≤ M)，如果從第 l_i 個字符到第 r_i 個字符之間至少包含一個 1，則將 a_i 加到得分中。 求字符串的最高得分。

限制： 所有輸入都是整數。 1 ≤ N ≤ 2 × 10^5 1 ≤ M ≤ 2 × 10^5 1 ≤ l_i ≤ r_i ≤ N |a_i| ≤ 10^9

X - Tower

你有 N 個積木。 每個積木都有一個編號 1, 2, …, N。 對於每個 i (1 ≤ i ≤ N)，積木 i 的重量是 wi，堅固度是 si，價值是 vi。 太郎打算從 N 個積木中選擇一些，將它們以任意順序堆疊成塔。 這個塔必須滿足以下條件：對於塔中的每個積木 i，堆疊在積木 i 上的積木的總重量必須小於或等於 si。

找出塔中積木的價值總和的最大值。

條件

  • 所有輸入都是整數。
  • 1 ≤ N ≤ 10^3
  • 1 ≤ wi, si ≤ 10^4
  • 1 ≤ vi ≤ 10^9

Y - Grid 2

有一個 H 行、W 列的網格。

我們用 (i, j) 表示網格中從上數第 i 行、從左數第 j 列的格子。

網格中有 N 個格子 (r₁ , c₁), (r₂ , c₂), …, (rₙ , cₙ) 是牆壁格子，其餘的格子都是空的。

保證格子 (1, 1) 和 (H, W) 是空的。

太郎君從格子 (1, 1) 出發，重複向右或向下移動到相鄰的空格子，試圖到達格子 (H, W)。

從格子 (1, 1) 到 (H, W) 太郎君的路徑有多少種？ 求出模 10⁹ + 7 的餘數。

條件

  • 所有輸入都是整數。
  • 2 ≤ H, W ≤ 10⁵
  • 1 ≤ N ≤ 3000
  • 1 ≤ rᵢ ≤ H
  • 1 ≤ cᵢ ≤ W
  • 格子 (rᵢ, cᵢ) 都彼此不同。
  • 格子 (1, 1) 和 (H, W) 是空的。

Z - Frog 3

有 N 個平台。 平台編號為 1, 2, …, N。 對於每個 i (1 ≤ i ≤ N)，平台 i 的高度為 h_i。 這裡， h_1 < h_2 < … < h_N。 最初，青蛙在平台 1 上。 青蛙重複以下行動若干次，試圖到達平台 N。 當青蛙在平台 i 上時，它跳到平台 i + 1, i + 2, …, N 中的任何一個。 此時，如果跳到的平台是 j，則需要支付成本 (h_j - h_i)^2 + C。 求青蛙到達平台 N 之前需要支付的成本總和的最小值。

條件：

  • 所有輸入均為整數。
  • 2 ≤ N ≤ 2 × 10^5
  • 1 ≤ C ≤ 10^{12}
  • 1 ≤ h_1 < h_2 < … < h_N ≤ 10^6