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…

CFR 19 B. Checkout Assistant ( DP )

Problem - 19B - Codeforces題意: 有 N 種商品各一個,若購買第 i 種商品,需要花費 C[ i ] 單位的錢,但是可以得到 T[ i ] 單位的店員不注意的時間,而店員不注意的時間每單位可以供你偷一件尚未購買的商品。問你最少要付多少錢才能獲得所有商品。資料規模…

CFR 790 C. Bear and Company ( DP )

Problem - C - Codeforces題意: 給一個長度為 N 的大寫英文字母組成的字串,一次操作可以將任一兩相鄰字符交換,問最少要多少次交換才能使得 "VK" 不以子字串形式出現。資料規模: The first line of the input contains an integer n (1 ≤ n ≤ 75) — the l…

CFR 13 C. Sequence ( DP )

Problem - 13C - Codeforces完全就是同一個題 只是這題要滾動才不會 MLE,然後詢問的是非遞減,所以不需要用到減下標的技巧。題意: 給一個陣列 A,可以任意讓值 +1 或 -1 任意多次,問最少要幾次才能將 A 變成非遞減數列。資料規模: MAXA ≤ 1e9 N ≤ 5000 T…

CFR 11 D. A Simple Task ( DP, Bitmask, Hamiltonian Walk )

Problem - 11D - Codeforces題意: 給一個無向圖。問有多少個簡單環 ( 無重複經過的點的環 )。資料規模: N ≤ 19 TL: 2000 ms解法: 考慮一個環,選定一個點 ( 這裡用編號最小的點 ) 切開之後變成一條鍊,假設原本是 abcd 這樣的環,那其實可以用點的集合和…

CFR 8 C. Looking for Order ( Bitmask, DP )

Problem - 8C - Codeforces題意: 給原點 ( sx, sy ),以及 N 個座標 X, Y。每次至多選兩個座標,依序拜訪完後,回到原點。問最好的路徑,使得路徑長最小。兩個座標的路徑長為歐幾里德距離的平方。資料規模: The first line of the input file contains the…

IOI 2016 Paint ( DP )

http://ioinformatics.org/locations/ioi16/contest/day2/paint/paint-TWN.pdf 1959 - [IOI 2016] Paint | TIOJ INFOR Online Judge題意: 給一個序列含 '.', 'X', '_',分別代表該位置的字符為未知、必為黑色、必為白色。再給 K 個數字 C[],代表由左到右看…

CFR 321 E. Ciel and Gondolas ( DP, Monotonic, Divide and Conquer )

Problem - E - Codeforces題意: 給一個矩陣,表示每對人之間的憎恨值。現在要把人划分為 K 群,每群必須都是連續編號的人。一個群的憎恨值貢獻是所有編號的有序對的憎恨值總和。求最少憎恨值總和。資料規模: The first line contains two integers n and k…

CFR 632 E. Thief in a Shop ( DP )

Problem - E - Codeforces題意: 有 N 個價值的物品,每個都有無限多個。輸出拿恰好 K 個物品可以產生出的所有值。資料規模: The first line contains two integers n and k (1 ≤ n, k ≤ 1000) — the number of kinds of products and the number of produc…

Yuki 243 出席番号(2) ( DP, Inclusion Exclusion )

No.243 出席番号(2) - yukicoder題意: 有 N 位可分別的學生,現在你要分配 0 ~ N - 1 的座位給他們。每個學生都有一個不喜歡的座位編號。求每個人都不作到不喜歡的座位編號的方案數,對 1e9 + 7 取模。資料規模: 生徒の数Nが最初の行で与えられる。1≤N≤500…

CFR 9 D. How many trees? ( DP )

Problem - D - Codeforces題意: 問 N 個節點組成的二叉樹,深度不少於 H 的方案有幾種。資料規模: H ≤ N ≤ 35解法: dp[ i ][ j ] : N 個節點的二叉樹,深度等於 H 的方案數 兩種轉移,首先當前的根是一定要的,一種是左空或又空,另一種是兩個都非空。時…

CFR 314 C. Sereja and Subsequences ( DP, BIT )

Problem - 314C - Codeforces題意: 給一個 N 個數組成的數列 A。現在有人把 A 的所有相異的非遞減子序列都生出來了。輸出,對這些子序列分別求,不比該子序列的字典序大的所有子序列的方案數,的總和,對 1e9 + 7 取模。資料規模: The first line contains…

CFR 383 D. Antimatter ( DP )

Problem - D - Codeforces題意: 給一個 N 個正整數組成的 A 數列。可以選一個連續區間,並決定每個數值分別的正負號,但其總和必須為 0 才合法。問有幾種合法的選取方式,選取方式相異若左界或右界不同,或任意一個元素分配到的正負號不同。輸出方案數對 1e…

CFR 404 D. Minesweeper 1D ( DP )

Problem - 404D - Codeforces題意: 給一個字符串,裡面只有 0, 1, 2, *, ? 五種符號。如果是數字,表示左右的 * 個數加起來一定有那麼多。如果是 ? 代表未確定。求有幾種 ? 的代入方式使得序列合法,對 1e9 + 7 取模。資料規模: The first line contains s…

CFR 431 D. Random Task ( Binary Search, Digit DP )

Problem - 431D - Codeforces題意: 給 M, K。求一個 N,滿足 1 ≤ N ≤ 1e18 且在二進制下,[ N + 1, 2 * N ] 中恰有 M 個數恰有 K 個 1。資料規模: The first line contains two space-separated integers, m and k (0 ≤ m ≤ 1e18; 1 ≤ k ≤ 64).解法: 直覺…

CFR 156 C. Cipher ( DP )

Problem - 156C - Codeforces題意: T 筆測資。每次給一個字串。有一種操作可以進行:選取兩個不同位置的字符,一個變成字典序小一的字符,另一個變成字典序大一的字符。特別的,a 沒有字典序小一的字符,z 沒有字典序大一的字符,而沒有相應的字符就不能進…

CFR 768 E. Game of Stones ( SG Value, DP )

Problem - 768E - Codeforces題意: N 堆石頭,輪流取,不能取的輸。對於某一堆石頭,不能拿走同個數量的石頭兩次。求後手勝敗。資料規模: First line consists of a single integer n (1 ≤ n ≤ 1e6) — the number of piles. Each of next n lines contains…

CFR 507 D. The Maths Lecture ( DP )

Problem - D - Codeforces題意: 求長度為 N 且沒有領導 0 的正整數中,有多少數字存在一個非 0 的後綴 y,使得 k 整除 y。輸出方案術對 m 取模。資料規模: Input consists of three integers n, k, m (1 ≤ n ≤ 1000, 1 ≤ k ≤ 100, 1 ≤ m ≤ 1e9).解法: dp[…

POJ 3866 Exclusive Access 2 ( Dilworth Theorem, DP, bitmask )

3866 -- Exclusive Access 2題意: 給一個 N 個無向邊的圖。求一種方案使所有邊定向,並有最短的最長路徑 ( 即不存在環 )。無法到達的點對之間的路徑長不須考慮。資料規模: N ≤ 100 節點為 [ L, Z ] 間的大寫英文字母,數量不超過 15。 TL: 5000 ms ML: 655…

POJ 2127 Greatest Common Increasing Subsequence ( DP )

2127 -- Greatest Common Increasing Subsequence題意: 給兩個數列 A, B,長度分別為 N, M,求最長公共遞增子序列。資料規模: 元素大小在 int32 範圍 N, M ≤ 500 TL: 2000 ms解法: 顯然可以定義 O( N^3 ) 的 dp,但這裡考慮 O( N^2 )。 dp[ i ][ j ] : B[…

IOICJ 109 Big Tower ( DP, Deque )

Problem Description: There is a tower with N floors, each floor having M rooms in order. One receives score S[ i ][ j ] when being at the j'th room of the i'th floor. You start at the X'th room at the first floor. Your objective is to trav…