sigman

P3694 邦邦的大合唱站隊

\(n\) 個偶像排成一列，他們來自 \(m\) 個不同的樂隊。每個團隊至少有一個偶像。

現在要求重新安排隊列，使來自同一樂隊的偶像連續的站在一起。重新安排的辦法是，讓若干偶像出列（剩下的偶像不動），然后讓出列的偶像一個個歸隊到原來的空位，歸隊的位置任意。

請問最少讓多少偶像出列？

此題是狀壓dp。
因為 \(n≤10^5,m≤20\)，考慮從組別考慮。我們可以將屬于同一個組的看作一個整體，那么最后相當于一個長度為 \(m\) 的數列。我們記 \(f_i\) 表示狀態為 \(i\) 下排在前面的最小出隊人數，從左往右 \(1\) 代表此組已經排好。對于每一組，它的人數記為 \(n_i\)，那么我們在前面放置排好的這些組，長度為 \(L=\sum_{i=1}^{n}[S\& 2^{i-1}]\times n_i\)，我們枚舉排在最后的組 \(i\)，那么它所占的區間就是 \([L-n_i+1,L]\)，我們只需要看這個區間里原本有多少不是屬于組 \(i\) 的即可，這一部分采用前綴和優化。記 \(s_{i,j}\) 表示前 \(i\) 中不屬于組 \(j\) 的個數。那么我們的轉移方程即為 \(f_i=\min\{f_{i-2^{j-1}}+s_{L,j}-s_{L-n_j}\}\)。

P1370 Charlie的云筆記序列

某天，Charlie 將收藏的題目抽象為一個序列。\(a=[a_1,a_2,a_3,\cdots,a_{n-1},a_n]\)。

Charlie 對序列 \([a_i]\) 定義了一個函數 \(F(l,r)\)，表示序列 \(a[l:r]\) 的本質不同的子序列個數。特別地，一個空序列也被當作一個本質不同的子序列。

長度為 \(n\) 的序列 \(a\) 和長度為 \(m\) 的序列 \(b\) 被稱作本質不同的，當且僅當 \(n\neq m\)，或存在 \(i\)，使得 \(a_i \neq b_i\)。反之，則稱這 \(2\) 個序列是本質相同的。

現在 Charlie 想知道，\(\sum _{1\le l\le r\le n} F(l,r)\) 的值是多少。由于這個數可能很大，請輸出它對 \(998244353\) 取模后的結果。

線性 dp。
記 \(f_i\) 表示 \(\sum_{j=i}^{n}F(i,j)\)，那么答案為 \(\sum_{i=1}^{n}f_i\)。首先如果序列的每一個數都不同，那么顯然 \(f_i=2\times f_{i+1}+2\)，原因是前面 \([i+1,n]\) 所能產生的 \(f_{i+1}\) 個子序列本身可以作為答案的一部分，然后這 \(f_{i+1}\) 個子序列接上 \(a_i\) 又可以產生 \(f_{i+1}\) 個，然后考慮 \(a_i\) 本身和空集，總共是 \(2\times f_{i+1}+2\)。接下來考慮去重。如果存在 \(a_i=a_j\)，\(i<j\)，那么統計 \(f_i\) 的時候 \([j+1,n]\) 區間所產生的 \(f_{j+1}\) 個子序列和 \(a_j\) 接上與和 \(a_i\) 接上效果是一樣的，這樣我們重復計算了 \(f_{j+1}\) 個，所以減去，然后 \(a_i\) 和 \(a_j\) 本身兩個單獨的又算了一遍，所以我們需要減去 \(f_{j+1}+1\)。由于我們每一次出現重復的都減去了，所以對于每一個 \(i\)，我們不需要找前面所有與 \(a_i\) 相同的，只需要找第一個與 \(a_i\) 相同的即可，因為前面的已經減去了。

P1283 平板涂色

CE 數碼公司開發了一種名為自動涂色機（APM）的產品。它能用預定的顏色給一塊由不同尺寸且互不覆蓋的矩形構成的平板涂色。

為了涂色，APM 需要使用一組刷子。每個刷子涂一種不同的顏色 \(C_i\) 。APM 拿起一把有顏色 \(C_i\) 的刷子，并給所有顏色為 \(C_i\) 且符合下面限制的矩形涂色：

為了避免顏料滲漏使顏色混合，一個矩形只能在所有緊靠它上方的矩形涂色后，才能涂色。例如圖中矩形 \(F\) 必須在 \(C\) 和 \(D\) 涂色后才能涂色。注意，每一個矩形必須立刻涂滿，不能只涂一部分。

寫一個程序求一個使 APM 拿起刷子次數最少的涂色方案。注意，如果一把刷子被拿起超過一次，則每一次都必須記入總數中。

看到數據范圍\(C_i≤20,N≤16\) 想到狀壓 dp。設狀態 \(f_{i,j}\) 表示矩陣涂色的狀態為 \(i\)，當前涂到 \(j\) 顏色的最少次數。我們將一次性將所有能涂的相同顏色的矩陣全涂好色拆分成一個一個涂，即我們可以從前面相同顏色轉移過來不耗費任何代價，也可以從不同顏色轉移過來，耗費 \(1\) 的代價。設當前涂的顏色 \(j\) 的矩陣編號為 \(k\)，方程為 \(f_{i,j}=\min\{f_{i-2^{k-1},l}+1\},l≠j\)，\(f_{i,j}=\min\{f_{i-2^{k-1},j}\}\)。其余細節較多，我們需要處理每一個矩陣需要哪些矩陣涂好色以后才能涂。