0w1

DP

ARC 074 E - RGB Sequence ( DP )

E: RGB Sequence - AtCoder Regular Contest 074 | AtCoder題意: N 個格子一排。 有三種顏色可以塗。 M 條限制,表示 [ L, R ] 中要有 X 種顏色。 求方案數模 1e9 + 7。制約: 1≤N≤300 1≤M≤300 1≤li≤ri≤N 1≤xi≤3解法: dp[ i ][ j ][ k ]:第 { 1, 2, 3 } …

HE Zulu visits Wonderland ( DP )

https://www.hackerearth.com/challenge/competitive/may-circuits-17/algorithm/zulu-visits-wonderla-1/題意: N 層的地下迷宮,M 種物品。 在時間 x,你能拿第 i 個物品若且唯若所有 Level 比 Level[ i ] 小的物品的過期時間不早於 x,並且 x + Time[ i ]…

CFR 611 D. New Year and Ancient Prophecy ( DP, Hash, LCP )

Problem - 611D - Codeforces題意: 給你一個大數。要求分割成若干個數字,滿足嚴格遞增,而且沒有領導 0。 問方案數對 1e9 + 7 取模。制約: 1 ≤ N ≤ 5000 保證第一個字符不為 '0'。解法: dp[ i ][ j ]:最後一個數字是 S[ i : j ] 時的方案數。 想知道 dp…

CFR 62 E. World Evil ( Flow, Mincut, DP, bitmask )

Problem - 62E - Codeforces題意: 給一個多角形柱體形成的網路,問最大流是多少。 起點是上面的面的所有點,匯點是下面的面的所有點。制約: 2 ≤ N ≤ 5 2 ≤ M ≤ 1e5 解法: 顯然不能暴力跑網路流算法。 考慮用 dp 求解。 最大流不好求,求最小割。 考慮水平…

CFR 811 C. Vladik and Memorable Trip ( DP )

Problem - 811C - Codeforces 題意: 給長度 N 的數列 A[]。你想要取出若干個連續數列,使得每個數列中相異元素的 XOR 和,之和最大。 但是有個條件,如果某個元素 x 在取出的某個數列裡,那麼所有元素 x 都必須在該數列中。制約: 1 ≤ N ≤ 5000 0 ≤ A[ i ] …

CFR 797 F. Mice and Holes ( DP, Monotonous, Divide and Conquer Optimization, or Deque Optimization )

Problem - F - Codeforces題意: 有 N 隻老鼠,用座標描述。有 M 個洞,用座標和容量描述。一隻位於座標 x 的老鼠進到位於座標 y 的洞裡要花費 abs( x - y )。問最小花費總和為何,才能使所有老鼠進洞。制約: 1 ≤ N, M ≤ 5000 abs( X[ i ] ), abs( P[ i ] )…

CFR 51 D. Beautiful numbers ( Digit DP )

Problem - D - Codeforces題意: 問 [ L, R ] 之間有多少整數,是可以被自身的所有非零數位整除。制約: T ≤ 10 1 ≤ L, R ≤ 9e18解法: 考慮 [ 1, x ] 的動態規劃: 一個顯然的狀態可以這樣定義: dp[ i ][ j ][ k ][ l ]: 考慮前 i 位,模 lcm( 1, 2, .. 9 …

ARC 073 F - Many Moves ( DP, Segment Tree )

F: Many Moves - AtCoder Regular Contest 073 | AtCoder題意: 在一個一維的棋盤上,你有兩顆棋,一顆在 A 位置,另一顆在 B 位置。有 Q 次操作,第 i 次操作後你必須移動棋子使得至少其中一個佔據 X[ i ]。棋子移動的花費是移動的距離。問 Q 次操作後,可…

ARC 073 D - Simple Knapsack ( DP )

D: Simple Knapsack - AtCoder Regular Contest 073 | AtCoder題意: 有 N 個物品要做 01 背包問題。背包容量 W,要求價值最大。注意有個特殊限制:所有物品的容量和第一個物品的容量的差不超過 3。制約: 1≦N≦100 1≦W≦1e9 1≦wi≦1e9 すべての i=2,3,…,N につ…

CFR 803 E. Roma and Poker ( DP )

Problem - E - Codeforces題意: 你在玩遊戲,一場有三種結果,勝/平/敗。你知道當你的勝利的場數和敗北的場數的絕對差在 K 以上時,會立刻退出遊戲。現在你有一個序列描述 N 場遊戲,而你知道你打完這 N 場後退出。有些紀錄被塗成 '?',要你復原出一個合理…

Yuki 162 8020運動 ( DP )

No.162 8020運動 - yukicoder題意: 你上下各有一排 14 個連續的牙齒。 你現在 A 歲,你想知道你在 80 歲時,期望會有多少顆牙齒剩下。 牙齒掉落的機率是 P[ 左邊的牙齒是否剩下 + 右邊的牙齒是否剩下 ]。解法: 考慮動態規劃: dp[ i ][ j ][ k ] : 經過 i …

CFR 486 E. LIS of Sequence ( DP, Fenwick Tree )

Problem - E - Codeforces題意: 給一個數列,對每一個值輸出: 1 if 它不屬於任何一個 LIS 2 if 它屬於某個 LIS,但沒有它也存在相同長度的 LIS 3 if 拔掉它的話 LIS 長度會改變制約: N ≤ 1e5 A ≤ 1e5解法: 用 dp 跟 BIT 的要領求出 st_len[ i ]: 以位置 …

Yuki 409 ダイエット ( Decision Monotonous, DP )

No.409 ダイエット - yukicoder題意: 有 N 天,第 i 天有重量 D[ i ] 單位的甜甜圈可以吃。你現在的重量是 W 單位,你想減肥,所以每天你可以選擇吃或不吃。如果吃了,你的體重就會增加吃掉的重量並歸零壓力值,否則你會減去 A 單位的重量但同時增加一個單…

ARC 072 E - Alice in linear land ( DP )

E: Alice in linear land - AtCoder Regular Contest 072 | AtCoder題意: 有一個車子在數線上的原點。目標是 D。依序有 N 個操作,d[ i ] 代表第 i 次操作的參數。每次操作將會使車子向目標的方向前進 d[ i ],但特別地,如果操作後不會接近,則該次操作無…

CFR 795 I. Composing Of String ( DP )

Problem - I - Codeforces題意: 有 N 種字串。你的目標字串為 target。問至少要連接幾次字串,才能使得這個大字串的子序列有 target。制約: The first line contains the integer n (1 ≤ n ≤ 50) — the number of strings in Stepan's set. The next n lin…

Yuki 497 入れ子の箱 ( DP )

No.497 入れ子の箱 - yukicoder題意: 給 N 個箱子,用三維各自的長度描述。一個箱子 i 容得下另一個箱子 j 若且唯若 X[ i ] > X[ j ] and Y[ i ] > Y[ j ] and Z[ i ] > Z[ j ]。問最多可以形成多少幾層的箱子。制約: 1≤N≤1000 1≤Xi,Yi,Zi解法: 依最小的…

Yuki 496 ワープクリスタル (給料日前編) ( DP )

No.496 ワープクリスタル (給料日前編) - yukicoder題意: 你有 N 顆一次性的魔法石頭,第 i 顆可以幫你在 X 軸上 + X[ i ],Y 軸上 + Y[ i ],但花費魔力 C[ i ]。你現在在 ( 0, 0 ),你的目的地是 ( Gx, Gy )。另外一種移動方式是向上或向右一格,花費 F。…

ARC 071 F - Infinite Sequence ( DP )

F: Infinite Sequence - AtCoder Regular Contest 071 | AtCoder題意: 問有多少無窮長度數列 A[] 滿足: 1. i 的下一個元素開始連續 A[ i ] 個皆相同 2. 對所有的 N ≤ i, j,A[ i ] = A[ j ] 輸出答案對 1e9 + 7 取模。制約: 1≤n≤1e6 n は整数解法: 首先…

CFR 244 B. Undoubtedly Lucky Numbers ( Digit DP, Python deepcopy() )

Problem - B - Codeforces題意: 給正整數 N,問有多少正整數不超過 N,在十進制下可以用不超過兩種數字表示。資料規模: N ≤ 1e9解法: dp[ i ][ j ][ k ][ l ]: 已處理 N 的長度為 i 的前綴,已使用的數字是 ( j, k ),滿足 j 用 python 的編程瓶頸在於宣…

CFR 768 D. Jon and Orbs ( DP, Probability )

Problem - D - Codeforces題意: 有 K 種卡片,每天都可以抽一張,抽到的種類機率分佈是隨機均勻。Q 筆詢問,問第幾天開始可以確定,對於任意一種卡片,有 P / 2000 的機率有至少一張。資料規模: First line consists of two space separated integers k, q…

CFR 768 C. Jon Snow and his Favourite Number ( DP )

Problem - C - Codeforces題意: 給一個長度為 N 的數列,要做 K 次操作。每次將數列排序後,奇數項 ( 1 based ) 和 X 做 xor,偶數項不變。問所有操作結束後,數列的長相。資料規模: First line consists of three integers n, k, x (1 ≤ n ≤ 1e5, 0 ≤ k ≤…

CFR 767 C. Garland ( Tree DP )

Problem - C - Codeforces題意: 給一棵節點帶權的樹。問是否存在一種分割方法,使得可以分成三個非空子樹,使得權重總和相同。輸出方案。資料規模: The first line contains single integer n (3 ≤ n ≤ 1e6) — the number of lamps in the garland. Then n…

CFR 788 C. The Great Mixing ( Math, bitset, DP )

Problem - C - Codeforces題意: 你的目標濃度是 N / 1000。你有 K 種液體,濃度分別為 a[ i ] / 1000。每一種液體可以用任意非負整數單位容量,求最小正整數,代表使用的總容量成功調配出目標濃度。資料規模: The first line contains two integers n, k (…

CFR 788 A. Functions again ( DP )

Problem - A - Codeforces題意: 給一個長度為 N 的數列 A[]。求最大的 f( l, r ),滿足 1 ≤ l 資料規模: The first line contains single integer n (2 ≤ n ≤ 1e5) — the size of the array a. The second line contains n integers a1, a2, ..., an (-1e9…

CFR 792 C. Divide by Three ( DP )

Problem - C - Codeforces題意: 給一個大數。問最少要刪除幾個數字才能使得剩下的數字為 3 的倍數。刪除後不得有前導 0。輸出方案。資料規模: 長度 ≤ 1e5解法: 刪除最少等價於保留最多。 dp[ i ][ j ] : 已考慮前 i 個數字,現在除以 3 餘 j,此時最大保…

CFR 786 A. Berzerk ( DP, Game )

Problem - A - Codeforces題意: 有 n 個星球,從 0 開始編號,順時針排成一圈。0 號星球是黑洞。兩人有各自的操作集合,遊戲採取輪流操作,每次操作時選擇自己的集合裡的一個數字,將怪獸順時針推移該數字那麼遠。第一位把怪獸推移至 0 號星球的人獲得勝利…

POI 2 Stage 2 Mudstock Bis ( Tree, DP )

http://main.edu.pl/en/archive/oi/2/mud題意: 首都在 ( 0, 0 ) 的位置,有 M 個人在首都裡。接著有 L 條線,每條線有若干個城市,依序用線上和前一個 ( 第一個城市和首都 ) 的距離以及人數描述。要求選一個點使得所有人到該點的總花費最小,一個人行走一單…

POI 2 Stage 2 The Right-Turn Drivers' Club ( DP, BFS )

http://main.edu.pl/en/archive/oi/2/kpk題意: 給一張圖,有若干障礙物,給始點和終點,問是否可以不左轉不倒回從始點走到終點,可以的話輸出最短路徑的方案。資料規模: In the first line of the standard input there are two integers separated by a s…

POI 2 Stage 1 Palindromes ( DP, Hash )

http://main.edu.pl/en/archive/oi/2/pal題意: 給一個字串,問最多和最少可以拆分成幾個偶數長度迴文,存在的話輸出方案。資料規模: The standard input contains one word consisting of at least 1 and at most 200 small letters of English alphabet. …

UVA 10818 - Dora Trip ( DP, bitmask )

UVa Online Judge題意: 給一個 R * C 的圖,保證周圍都是牆( # ),也不能拜訪 ( X ),起點在 ( S ),問在拜訪最多 ( * ) 的前提下,最短迴路的最小字典序序列序列是什麼。資料規模: The input file contains no more than 20 test cases. The details of e…