USACO競賽2020-2021新賽季已開啟 ，不少同學已進入最後的衝(chong) 刺準備階段，在瘋狂刷刷刷刷刷刷題~~~為(wei) 方便同學了解題目思路，奇思孵化準備了四期《USACO題解》專(zhuan) 題，提供 2019-2020賽季各級別晉級題目題解參考，希望能為(wei) 同學們(men) 提供有用的幫助。
1
題目1：Cow Gymnastics為(wei) 了提高健康水平，奶牛們(men) 開始進行體(ti) 操訓練了！Farmer John 選定了他最喜愛的奶牛 Bessie 來執教其他 N頭奶牛，同時評估她們(men) 學習(xi) 不同的體(ti) 操技術的進度。
K次訓練課的每一次（1≤K≤10），Bessie 都會(hui) 根據 N 頭奶牛的表現給她們(men) 進行排名（1≤N≤20）。之後，她對這些排名的一致性產(chan) 生了好奇。稱一對不同的奶牛是一致的，如果其中一頭奶牛在每次訓練課中都表現得都比另一頭要好。請幫助 Bessie 計算一致的奶牛的對數。輸入格式（文件名：gymnastics.in）：輸入的第一行包含兩(liang) 個(ge) 正整數 K 和 N。以下 K 行每行包含整數 1…N 的某種排列，表示奶牛們(men) 的排名（奶牛們(men) 用編號 1…N進行區分）。如果在某一行中 A 出現在 B 之前，表示奶牛 A 表現得比奶牛 B 要好。輸出格式（文件名：gymnastics.out）：輸出一行，包含一致的奶牛的對數。輸入樣例：3441 2 341 3 242 1 3輸出樣例：4一致的奶牛對為(wei) (1,4)、(2,4)、(3,4) 和 (1,3).題解先開兩(liang) 個(ge) 二維數組，一個(ge) 來存儲(chu) 數據，另一個(ge) 【i】【j】來存儲(chu) 第i天第j頭奶牛的排名，再通過暴力來求出個(ge) 數。
題目2：Where Am IFarmer John 出門沿著馬路散步，但是他現在發現可能迷路了！沿路有一排共 N 個(ge) 農(nong) 場（1≤N≤100）。不幸的是農(nong) 場並沒有編號，這使得 Farmer John 難以分辨他在這條路上所處的位置。然而，每個(ge) 農(nong) 場都沿路設有一個(ge) 彩色的郵箱，所以 Farmer John 希望能夠通過查看最近的幾個(ge) 郵箱的顏色來唯一確定他所在的位置。每個(ge) 郵箱的顏色用 A..Z 之間的一個(ge) 字母來指定，所以沿著道路的 N 個(ge) 郵箱的序列可以用一個(ge) 長為(wei) N 的由字母 A..Z 組成的字符串來表示。某些郵箱可能會(hui) 有相同的顏色。Farmer John 想要知道最小的 K 的值，使得他查看任意連續 K 個(ge) 郵箱序列，他都可以唯一確定這一序列在道路上的位置。
例如，假設沿路的郵箱序列為(wei) 'ABCDABC' 。Farmer John 不能令 K=3，因為(wei) 如果他看到了 'ABC'，沿路有兩(liang) 個(ge) 這一連續顏色序列可能所在的位置。最小可行的 K 的值為(wei) K=4，因為(wei) 如果他查看任意連續 4 個(ge) 郵箱，這一顏色序列可以唯一確定他在道路上的位置。
輸入格式（文件名：whereami.in）：
輸入的第一行包含 N，第二行包含一個(ge) 由 N 個(ge) 字符組成的字符串，每個(ge) 字符均在 A..Z 之內(nei) 。
輸出格式（文件名：whereami.out）：輸出一行，包含一個(ge) 整數，為(wei) 可以解決(jue) Farmer John 的問題的最小 K 值。
輸入樣例：
7ABCDABC
輸出樣例：
4
題解：
暫且稱“ABC”那樣有兩(liang) 個(ge) （或以上）完全相等的東(dong) 西為(wei) “小字符串”。可以得出，當小字符串長度=3時，k=4。所以我們(men) 就要求出最長的小字符串的長度，並且加一後輸出。
題目3：Livestock Lineup
每天，Farmer John 都要給他的 8 頭奶牛擠奶。她們(men) 的名字分別是 Bessie，Buttercup，Belinda，Beatrice，Bella，Blue，Betsy，和 Sue。不幸的是，這些奶牛相當難以伺候，她們(men) 要求 Farmer John 以一種符合 N 條限製的順序給她們(men) 擠奶（1≤N≤7）。每條限製的形式為(wei) “X 必須緊鄰著 Y 擠奶”，要求奶牛 X 在擠奶順序中必須緊接在奶牛 Y 之後，或者緊接在奶牛 Y 之前。
請幫助 Farmer John 求出一種滿足所有限製的奶牛擠奶順序。保證這樣的順序是存在的。如果有多種順序都滿足要求，請輸出字典序最小的一種。也就是說，第一頭奶牛需要是所有可能排在任意合法奶牛順序的第一位的奶牛中名字字典序最小的。在所有合法的以這頭字典序最小的奶牛為(wei) 首的奶牛順序中，第二頭奶牛需要是字典序最小的，以此類推。
輸入格式（文件名：lineup.in）
輸入的第一行包含 N。以下 N 行每行包含一句句子，以 "X must be milked beside Y" 的格式描述了一條限製，其中 X 和 Y為(wei) Farmer John 的某些奶牛的名字（上文列舉(ju) 了八個(ge) 可能的名字）。
輸出格式（文件名：lineup.out）：
請用 8 行輸出一個(ge) 奶牛的順序，每行輸出一頭奶牛的名字，滿足所有的限製。如果由多種順序符合要求，輸出字典序最小的奶牛順序。
輸入樣例：
3
Buttercup must be milked beside Bella
Blue must be milked beside Bella
Sue must be milked beside Beatrice
輸出樣例：
Beatrice
Sue
Belinda
Bessie
Betsy
Blue
Bella
Buttercup
題解：
用next_permutation函數模擬字典序從(cong) 小到大的情況，然後用map存放序號，判斷順序是否符合要求就可以！
2
題目1 ：MooBuzzFarmer John 的奶牛們(men) 最近成為(wei) 了一個(ge) 簡單的數字遊戲“FizzBuzz”的狂熱玩家。這個(ge) 遊戲的規則很簡單：奶牛們(men) 站成一圈，依次從(cong) 一開始報數，每頭奶牛在輪到她的時候報一個(ge) 數。如果一頭奶牛將要報的數字是 3 的倍數，她應當報“Fizz”來代替這個(ge) 數。如果一頭奶牛將要報的數字是 5 的倍數，她應當報“Buzz”來代替這個(ge) 數。如果一頭奶牛將要報的數字是 15 的倍數，她應當報“FizzBuzz”來代替這個(ge) 數。於(yu) 是這個(ge) 遊戲的開始部分的記錄為(wei) ：1, 2, Fizz, 4, Buzz, Fizz, 7, 8, Fizz, Buzz, 11, Fizz, 13, 14, FizzBuzz, 16由於(yu) 詞匯的匱乏，奶牛們(men) 玩的 FizzBuzz 中用“Moo”代替了 Fizz、Buzz、FizzBuzz。於(yu) 是奶牛版的遊戲的開始部分的記錄為(wei) ：1, 2, Moo, 4, Moo, Moo, 7, 8, Moo, Moo, 11, Moo, 13, 14, Moo, 16給定 NN（1≤N≤109），請求出這個(ge) 遊戲中第 N 個(ge) 被報的數。測試點性質：測試點 2-5 滿足 N≤106。輸入格式（文件名：moobuzz.in）輸入包含一個(ge) 整數 N。輸出格式（文件名：moobuzz.out）：輸出遊戲中被報出的第 N 個(ge) 數。輸入樣例：4輸出樣例：7第 4 個(ge) 被報的數是 7。前 4 個(ge) 被報的數是 1、2、4、7，因為(wei) 我們(men) 在奶牛說“Moo”時就會(hui) 跳過數字。解析題目大意：求從(cong) 一開始第n個(ge) 既不是三的倍數又不是五的倍數的數我們(men) 將所有 3 的倍數和 5的倍數去除，剩餘(yu) 的列表（報出的數）前段如下：1 2 4 7 8 11 13 14/16 17 19 22 23 26 28 29/31 32 34 37 38 41 43 44...設第 i 個(ge) 列表中的數為(wei) fi。上麵，/符號將列表分成了若幹部分，其中每一個(ge) 部分有 8 個(ge) 數。對於(yu) 每部分的最後一個(ge) 數找規律，易得如下公式（kk 為(wei) 正整數）：f8k = 15k-1得到這個(ge) 公式後，對於(yu) N 為(wei) 8 的倍數的情況，可以直接套用公式求解。如果不是呢？不妨設 N=8k+a（1≤a≤7），問題就轉化為(wei) 從(cong) 15k開始的被報出的第 a 個(ge) 數。由於(yu) a 很小，這一部分隻要暴力即可。
題目2：Meetings有兩(liang) 個(ge) 牛棚位於(yu) 一維數軸上的點 0 和 L 處（1≤L≤109）。同時有 N 頭奶牛（1≤N5⋅104）位於(yu) 數軸上不同的位置（將牛棚和奶牛看作點）。每頭奶牛 i 初始時位於(yu) 某個(ge) 位置 xi ，並朝著正向或負向以一個(ge) 單位每秒的速度移動，用一個(ge) 等於(yu) 1 或 −1 的整數di 表示。每頭奶牛還擁有一個(ge) 在範圍 [1,103]內(nei) 的重量。所有奶牛始終以恒定的速度移動，直到以下事件之一發生：如果奶牛 i 移動到了一個(ge) 牛棚，則奶牛 i 停止移動。
當奶牛 i 和 j 占據了相同的點的時候，並且這一點不是一個(ge) 牛棚，則發生了相遇。此時，奶牛 i 被賦予奶牛 j 先前的速度，反之亦然。注意奶牛可能在一個(ge) 非整數點相遇。
令 T 等於(yu) 停止移動的奶牛（由於(yu) 到達兩(liang) 個(ge) 牛棚之一）的重量之和至少等於(yu) 所有奶牛的重量之和的一半的最早時刻。請求出在時刻 0…T（包括時刻T）之間發生的奶牛對相遇的總數。測試點性質：測試點 2-4 滿足 N≤102，並且對所有 i，wi =1。測試點 5-7 滿足 N≤102。輸入格式（文件名：meetings.in）：輸入的第一行包含兩(liang) 個(ge) 空格分隔的整數 N 和 L。以下 N 行，每行包含三個(ge) 空格分隔的整數wi，xi 以及 di 。所有的位置 xixi 各不相同，並且滿足 0<xi <L。輸出格式（文件名：meetings.out）：輸出一行，包含答案。輸入樣例：3 51 1 12 2 -13 3 -1輸出樣例：2在這個(ge) 例子中，奶牛們(men) 按如下方式移動：①第一和第二頭奶牛於(yu) 時刻 0.5 在位置 1.5 相遇。此時第一頭奶牛擁有速度 −1，第二頭奶牛擁有速度 1。②第二和第三頭奶牛於(yu) 時刻 1 在位置 2 相遇。此時第二頭奶牛擁有速度 −1，第三頭奶牛擁有速度 1。③第一頭奶牛於(yu) 時刻 2 到達左邊的牛棚。④第二頭奶牛於(yu) 時刻 3 到達左邊的牛棚。⑤由於(yu) 到達牛棚的奶牛的總重量已經至少是所有奶牛的總重量的一半，這個(ge) 過程此時終止。如果繼續進行下去，第三頭奶牛將會(hui) 在時刻 4 到達右邊的牛棚。發生了恰好兩(liang) 次相遇。題解：首先對所有的牛按照位置排序，我們(men) 用兩(liang) 個(ge) 雙端隊列P,Q分別記錄朝右和朝左的牛的有序集合。每次將P隊尾離L的距離和Q隊頭到0的距離對比，選擇更近的那頭牛（它會(hui) 更早到牛棚）然後將它路徑上相遇的牛的重量全部往後移一個(ge) 位置一直循環下去，每次搞定一頭牛，直到到牛棚的牛的質量大於(yu) 總質量的一半停止這樣我們(men) 就得到了整個(ge) 過程的持續時間還沒完，我們(men) 利用這個(ge) 持續時間，計算如果兩(liang) 頭相對的牛相遇，他們(men) 的距離差必定≤2∗Time避免最後計算過程爆N2，我們(men) 用一個(ge) 單調隊列模擬一下即可。
題目3：Grass Planting S到了一年中Farmer John在他的草地裏種草的時間了。整個(ge) 農(nong) 場由N塊草地組成（1≤N≤105），方便起見編號為(wei) 1…N，由N−1條雙向的小路連接，每塊草地都可以經過一些小路到達其他所有的草地。 Farmer John當然可以在每塊草地裏種不同種類的草，但是他想要使得使用的草的種類數最小，因為(wei) 他用的草的種類數越多，他就需要負擔更高的花費。不幸的是，他的奶牛們(men) 對選擇農(nong) 場上的草表現得十分苛刻。如果兩(liang) 塊相鄰（由一條小路直接相連）的草地種了同一種草，或者即使是兩(liang) 塊接近相鄰（均可由一條小路直接連向同一塊草地）的草地，那麽(me) 奶牛們(men) 就會(hui) 抱怨她們(men) 進餐的選擇不夠多樣。Farmer John能做的隻能是抱怨這些奶牛，因為(wei) 他知道她們(men) 不能被滿足的時候會(hui) 製造多大的麻煩。請幫助Farmer John求出他的整個(ge) 農(nong) 場所需要的最少的草的種類數。輸入格式輸入的第一行包含N。以下N−1行每行描述了一條小路連接的兩(liang) 塊草地。輸出格式輸出Farmer John需要使用的最少的草的種類數輸入樣例1 24 32 3輸出樣例3解析考慮在一個(ge) 點的父節點，子節點，這個(ge) 點本身塗不同的顏色。而在這個(ge) 點的孫節點（或祖節點）可以用同一個(ge) 顏色集合來塗色。所以統計每個(ge) 點的度，找到度最大的點，輸出 這個(ge) 點的度+1。
3
題目1：Milk PumpingFarmer John 最近為(wei) 了擴張他的牛奶產(chan) 業(ye) 帝國而收購了一個(ge) 新的農(nong) 場。這一新的農(nong) 場通過一個(ge) 管道網絡與(yu) 附近的小鎮相連，FJ 想要找出其中最合適的一組管道，將其購買(mai) 並用來將牛奶從(cong) 農(nong) 場輸送到小鎮。這個(ge) 管道網絡可以用 NN 個(ge) 接合點（管道的端點）來描述，將其編號為(wei) 1…N（2≤N≤1000）。接合點 1 表示 FJ 的農(nong) 場，接合點 N 表示小鎮。有 MM 條雙向的管道（1≤M≤1000），每條連接了兩(liang) 個(ge) 接合點。使用第 i 條管道需要 FJ 花費 ci 美元購入，可以支持每秒 fi 升牛奶的流量。FJ 想要購買(mai) 一條管道組成一條單一路徑，路徑的兩(liang) 端點分別為(wei) 接合點 1 和 NN。這條路徑的花費等於(yu) 路徑上所有管道的費用之和。路徑上的流量等於(yu) 路徑上所有管道的最小流量（因為(wei) 這是沿這條路徑輸送牛奶的瓶頸）。FJ 想要最大化路徑流量與(yu) 路徑花費之比。保證存在從(cong) 1 到 N之間的路徑。測試點性質：測試點 2-5 滿足 N,M≤100。輸入格式（文件名：pump.in）：輸入的第一行包含 N 和 M。以下 M 行每行以四個(ge) 整數描述一條管道：a 和 b（管道連接的兩(liang) 個(ge) 不同的接合點），c（管道的花費），以及 f（管道的流量）。花費和流量均為(wei) 範圍 1…1000之內(nei) 的正整數。輸出格式（文件名：pump.out）：輸出 106乘以最優(you) 解的值，並向下取整（也就是說，如果這個(ge) 數本身不是整數，輸出小於(yu) 它的最接近它的整數）。輸入樣例：3 22 1 2 42 3 5 3輸出樣例：428571在這個(ge) 例子中，僅(jin) 由一條路徑從(cong) 1 到 N。它的流量為(wei) min(3,4)=3=3，花費為(wei) 2+5=7。解析有兩(liang) 個(ge) 條件，考慮先枚舉(ju) f。既然要使分母∑ci 最小，那不相當於(yu) 以 c 為(wei) 邊權跑最短路？於(yu) 是我們(men) 可以跑 dijkstra 或 spfa。不過為(wei) 了達到枚舉(ju) f 起的限製作用，我們(men) 在每次鬆弛操作之前，要先判斷這條邊的限製是否大於(yu) f。否則不把這條邊計算的最短路中，因為(wei) 它不滿足當前限製。跑完最短路更新答案即可。這裏使用堆優(you) 化的 dijkstra，時間複雜度約為(wei) O(n2log n)，可以通過本題。實現細節①建圖注意是無向圖。②由於(yu) 需要多次跑最短路，記得清空某些數組。③重載priority_queue的時候，符號不要寫(xie) 錯。
題目2：Milk VisitsFarmer John 計劃建造 N（1≤N≤105）個(ge) 農(nong) 場，用 N−1條道路連接，構成一棵樹（也就是說，所有農(nong) 場之間都互相可以到達，並且沒有環）。每個(ge) 農(nong) 場有一頭奶牛，品種為(wei) 更賽牛或荷斯坦牛之一。Farmer John 的 M 個(ge) 朋友（1≤M≤105）經常前來拜訪他。在朋友 i 拜訪之時，Farmer John 會(hui) 與(yu) 他的朋友沿著從(cong) 農(nong) 場Ai 到農(nong) 場 Bi 之間的唯一路徑行走（可能有Ai =Bi）。除此之外，他們(men) 還可以品嚐他們(men) 經過的路徑上任意一頭奶牛的牛奶。由於(yu) Farmer John 的朋友們(men) 大多數也是農(nong) 場主，他們(men) 對牛奶有著極強的偏好。他的有些朋友隻喝更賽牛的牛奶，其餘(yu) 的隻喝荷斯坦牛的牛奶。任何 Farmer John 的朋友隻有在他們(men) 訪問時能喝到他們(men) 偏好的牛奶才會(hui) 高興(xing) 。請求出每個(ge) 朋友在拜訪過後是否會(hui) 高興(xing) 。測試點性質：測試點 2-5 滿足 N≤103,M≤2⋅103。輸入格式（文件名：milkvisits.in）：輸入的第一行包含兩(liang) 個(ge) 整數 N 和 M。第二行包含一個(ge) 長為(wei) N 的字符串。如果第 i 個(ge) 農(nong) 場中的奶牛是更賽牛，則字符串中第 i 個(ge) 字符為(wei) 'G'，如果第 i 個(ge) 農(nong) 場中的奶牛是荷斯坦牛則為(wei) 'H'。以下 N−1行，每行包含兩(liang) 個(ge) 不同的整數 X 和 Y（1≤X,Y≤N），表示農(nong) 場 X 與(yu) Y 之間有一條道路。以下 M行，每行包含整數 Ai ，Bi，以及一個(ge) 字符 CiCi。Ai 和 Bi 表示朋友 i 拜訪時行走的路徑的端點，Ci 是 'G' 或 'H' 之一，表示第 i 個(ge) 朋友喜歡更賽牛的牛奶或是荷斯坦牛的牛奶。輸出格式（文件名：milkvisits.out）：輸出一個(ge) 長為(wei) M的二進製字符串。如果第 i 個(ge) 朋友會(hui) 感到高興(xing) ，則字符串的第 i 個(ge) 字符為(wei) '1'，否則為(wei) '0'。輸入樣例：5 5HHGHG1 22 32 41 51 4 H1 4 G1 3 G1 3 H5 5 H輸出樣例：10110在這裏，從(cong) 農(nong) 場 1 到農(nong) 場 4 的路徑包括農(nong) 場 1、2 和 4。所有這些農(nong) 場裏都是荷斯坦牛，所以第一個(ge) 朋友會(hui) 感到滿意，而第二個(ge) 朋友不會(hui) 。解析考慮求點u到點v的路徑上是否有顏色為(wei) c的路徑。我們(men) 可以考慮遍曆這條路徑，我們(men) 需要求這兩(liang) 個(ge) 點的lca 然後從(cong) 兩(liang) 個(ge) 點分別遍曆到lca，並且檢查路徑上是否有顏色為(wei) c的節點。這樣很明顯，複雜度是O(n2+nlogn)的，在使用樹剖之後，我們(men) 做到了小常數求lca，但是這樣遠遠不夠。這個(ge) 時候，我們(men) 考慮優(you) 化尋找某種顏色的節點的方法，注意到在重鏈上的dfn序是連續的，所以事實上我們(men) 是在每條重鏈上的[dfn[top[u]],dfn[u]]區間內(nei) 尋找顏色為(wei) c的節點。可以將所有顏色為(wei) c的節點的dfn序存到一個(ge) vector之中，然後問題就轉化成了問一個(ge) 數列中，是否存在一個(ge) 數，在[dfn[top[u]],dfn[u]]內(nei) 。這個(ge) 問題可以通過二分求大於(yu) 等於(yu) dfn[top[u]]的最小的數x 判斷x < dfn[u]是否成立就可以解決(jue) 這個(ge) 問題，這樣對於(yu) 每個(ge) 鏈上做到了O(logn)的判斷是否有顏色為(wei) c的節點。這樣的總複雜度是O(nlog2n)。
題目3： Moortal CowmbatBessie 玩格鬥遊戲真牛快打已經有很長時間了。然而，最近遊戲開發者發布了一項更新，這迫使 Bessie 改變她的打法。遊戲總共使用 M 個(ge) 按鍵，標記為(wei) 前 M 個(ge) 小寫(xie) 字母（1≤M≤26）。Bessie 在遊戲中最喜歡的組合鍵是一個(ge) 長為(wei) N 的按鍵字符串 S（1≤N≤105）。然而，由於(yu) 最近的更新，現在每種組合鍵必須由一些“連擊”所組成，其中連擊的定義(yi) 為(wei) 相同的按鍵連續按下至少 K 次（1≤K≤N）。Bessie想要修改她最喜歡的組合鍵，創造一個(ge) 同樣長為(wei) N 的新組合鍵，然而這一新組合鍵由按鍵連擊所組成，以適應規則的變化。Bessie 需要消耗 aij天來訓練她在組合鍵中某個(ge) 特定的位置用按鍵 j 來取代按鍵 i（也就是說，將 S 中的某個(ge) 特定的字符由 i 變為(wei) j 的代價(jia) 為(wei) aij）。注意有可能將按鍵 i 換成某種中間按鍵 k 然後再從(cong) 按鍵 k 換成按鍵 j 會(hui) 比直接從(cong) 按鍵 i 換成按鍵 j 消耗更短的時間（或者更一般地說，可能有一條起點為(wei) i 終點為(wei) j 的更改路徑給出了從(cong) 按鍵 i 最終更改為(wei) 按鍵 j 的最小總代價(jia) ）。幫助 Bessie 求出她創建一個(ge) 滿足新要求的組合鍵所需要的最小天數。測試點性質：測試點 2-4 滿足 N≤1000,K≤50。測試點 5-8 滿足 N≤30,000,K≤50。輸入格式（文件名：cowmbat.in）：輸入的第一行包含 N，M 和 K。第二行包含 S，最後 M 行包含一個(ge) M×M 的數字方陣 aijaij，其中 aij為(wei) 一個(ge) 範圍為(wei) 0…10000的整數，並且對於(yu) 所有的 i，有 aii=0。輸出格式（文件名：cowmbat.out）：輸出一個(ge) 整數，表示 Bessie 將她的組合鍵改為(wei) 一個(ge) 滿足新要求的新的組合鍵所需要的最小天數。輸入樣例：5 5 2abcde0 1 4 4 42 0 4 4 46 5 0 3 25 5 5 0 43 7 0 5 0輸出樣例：5在這個(ge) 例子中的最優(you) 方案是將 a 改為(wei) b，將 d 改為(wei) e，再將兩(liang) 個(ge) e 都改為(wei) c。這總共消耗1+4+0+0=5天，最終的組合鍵為(wei) bbccc。解析給定一個(ge) 字符串和一個(ge) M×M 的矩陣 a，表示可以消耗ai,j 的代價(jia) 把字符 i改成字符 j，求把原字符串改成每個(ge) 連續段長度都不小於(yu) K的最小代價(jia) 。n,K≤105,M≤26首先直接用原矩陣的交換方法不一定最優(you) ，拿到手先跑一遍 floyd。然後考慮 dp ，fi表示前 i個(ge) 中每個(ge) 連續段都≥k 的最小代價(jia) ，顯然有轉移.fi=min{ fi+cost(i,j,c)} (j≤i−k)其中 cost(i,j,c) 表示把 [i,j]全都改成字符 cc的最小代價(jia) ，這個(ge) 可以前綴和預處理。觀察轉移，發現可以在枚舉(ju) 到 i 時再把 i-k的決(jue) 策加進去，這樣維護一個(ge) 前綴 min 即可做到 O(1)轉移。複雜度 O(n×M)。
【競賽報名/項目谘詢+微信：mollywei007】
評論已經被關(guan) 閉。