DP 基礎題亂做

惡補基礎 DP.

2025.10.22

CF1061C 多樣性

轉移是經典的子序列 DP，考慮前 \(i\) 個數，子序列長度為 \(j\) 的方案數. 轉移：

\[f_{i,j}=\begin{cases} f_{i-1,j-1}+f_{i-1,j}&j\mid a_i\\ f_{i-1,j}&otherwise. \end{cases} \]

可以滾動數組優化一維. 考慮優化，第二種轉移直接繼承，第一種轉移不必枚舉 \(j\)，可以 \(O(\sqrt v)\) 處理出所有約數，從大到小轉移（與 \(0/1\) 背包原理類似）. 總時間復雜度 \(O(n\sqrt v)\).

CF2121H 冰寶貝

看到范圍是區間，一個直接的想法是離散化. 然而我們可以換維，直接把值域當做 DP 值，把子序列長度開一維狀態來記錄. 另一個貪心的想法是我們一定要讓子序列末尾盡量小，于是設計出一個狀態：\(f_{i,j}\) 表示考慮前 \(i\) 個區間，不降子序列長度為 \(j\) 時末尾最小值，轉移：

\[f_{i,j}=\begin{cases} f_{i-1,j-1}&l_i\le f_{i-1,j-1}\le r_i\\ f_{i-1,j} &otherwise. \end{cases} \]

優化仍然可以先滾動一維. 從 \(f\) 下標的角度看轉移，就是區間 \([l_i,r_i]\) 整體右移了一位. 若當前最長子序列的末尾不大于 \(r_i\)，右移后不會有重疊的位置，最長子序列 \(+1\). 否則存在一個位置 \(p\) 重疊，考慮保留哪個更優. 注意到 \(f_j\) 顯然不降，于是應該刪掉原來 \(p\) 位置上的值，最長子序列長度不變.

考慮維護，實際上我們只關心查詢最長子序列的長度，維護在有序的一列數中插入一個數，刪除一個數，并且補位. 發現所有操作都可以用 multiset 維護，時間復雜度 \(O(\sum n\log n)\).

點擊查看代碼

#include<bits/stdc++.h>
using namespace std;

const int maxn = 2e5 + 10;
int T, n;

void solve() {
    cin >> n;
    multiset<int> s; s.insert(0);
    while(n--) {
        int l, r; cin >> l >> r;
        auto p = s.upper_bound(r);
        s.insert(l); if(p != s.end()) s.erase(p);
        cout << s.size() - 1 << " ";
    } cout << "\n";
    return;
}

int main() {
    ios :: sync_with_stdio(false); cin.tie(0); cout.tie(0);

    cin >> T; while(T--) solve();

    return 0;
}

AT_agc054_b [AGC054B] 貪心劃分

agc 特有的結論計數題，鑒定為純粹的腦筋急轉彎.

結論：確定兩人最終選擇的物品集合后，兩人拿物品的排列唯一確定，即二者構成雙射. 可能不難感受到正確性，然而獨立想到并不容易.

所以直接背包跑選 \(i\) 個物品湊到 \(sum\over2\) 的方案數，再賦予排列順序加起來即可. 時間復雜度 \(O(n\sum w_i)\).

AT_agc054_c [AGC054C] 粗略排序

神人題.

考慮對于一個排列怎么交換使其合法. 發現由于所有數都比 \(1\) 大，\(1\) 至少要挪到位置 \(k+1\)，除非本來就在 \(k+1\) 前面，同理可以推廣到數 \(i\) 至少要挪到 \(k+i\).

那么對于一個操作后的排列，\(p_i=i+k\) 的位置原來就只可能在區間 \([i+k,n]\)，乘起來即可. 時間復雜度 \(O(n)\).

2025.10.23

P1858 多人背包

要求背包的前 \(k\) 優解，那么第 \(i\) 優解一定是從第 \(i-1\) 解基礎上更新得到的. 考慮樸素 \(0/1\) 背包的轉移：

\[f_{i,j}\leftarrow \max_{j=w_i}^V (f_{i-1,j},f_{i-1,j-w_i}+v_i) \]

求第 \(i\) 解時，要么直接繼承第 \(i-1\) 解，要么用當前的物品去替換原來的容量更新價值. 所以一共有 \(2k\) 種情況，全部求出來取前 \(k\) 大更新即可.

然而也可以在線地做，觀察到兩種轉移值分別是長度為 \(k\) 的遞減序列，拿兩個指針掃即可. 時間復雜度 \(O(knV)\).

點擊查看代碼

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;

const int maxn = 2e2 + 10, maxv = 5e3 + 10, maxk = 55;
int K, V, n, v[maxn], w[maxn];
ll ans, f[maxv][maxk];

int main() {
    ios :: sync_with_stdio(false); cin.tie(0); cout.tie(0);

    cin >> K >> V >> n; for(int i = 1; i <= n; i++) cin >> w[i] >> v[i];
    memset(f, -0x3f3f, sizeof f);
    f[0][1] = 0;
    for(int i = 1; i <= n; i++) {
        for(int j = V; j >= w[i]; j--) {
            ll tmp[maxk];
            for(int k = 1, p1 = 1, p2 = 1; k <= K; k++) {
                if(f[j][p1] >= f[j - w[i]][p2] + v[i]) tmp[k] = f[j][p1++];
                else tmp[k] = f[j - w[i]][p2++] + v[i];
            } memcpy(f[j], tmp, sizeof f[j]);
        }
    } for(int i = 1; i <= K; i++) ans += f[V][i];
    cout << ans;

    return 0;
}

P4158 [SCOI2009] 粉刷匠

設 \(f_{i,j}\) 表示花 \(j\) 步填前 \(i\) 行能涂對的最多格子數. 發現這個東西根本轉移不了，要想轉移，我們還需要知道花若干步填一行最多能填多少個，設 \(g_{i,j,k}\) 表示第 \(i\) 行前 \(j\) 個數，花 \(k\) 步最多能涂多少格子，發現 \(f\) 的轉移形如背包，有：

\[f_{i,j}\leftarrow f_{i-1,j-t}+g_{i,m,t} \]

\(g_{i,j,k}\) 的轉移比較簡單粗暴，枚舉從前綴 \(x\) 處轉移過來，欽定 \((x,j]\) 全部涂成一個顏色，預處理出一種顏色個數的前綴和，可以直接算出另一種顏色的個數. 所以有轉移：

\[g_{i,j,k}\leftarrow \max_{x<j}\Big(g_{i,x,k-1}+\max(sum_j-sum_x,j-x-sum_j+sum_x)\Big) \]

總時間復雜度 \(O(nT+nm^3)\).

P8392 [BalticOI 2022] Uplifting Excursion

神秘題目.

首先有一個貪心是先把所有物品選了，然后從大到小刪除，因為小的選了比大的更優. 這時一定存在方案把 \(sum\) 控制在 \([L-m,L+m]\).

記錄下每個物品用了多少，考慮用剩下的物品把 \(sum\) 調整到 \(L\). 有結論是在調整過程中出現之前出現過的 \(sum\) 一定不會更優，因為原來求得的 \(sum\) 從最大值開始刪，得到的是最優解. 所以為了保證正確性，我們需要按物品從小到大添加. 由于值域限制為 \(O(m)\)，所以增減物品的次數是 \(O(m)\) 的，進一步的背包容量就為 \(O(m^2)\).

直接跑多重背包的二進制分組優化，時間復雜度 \(O(m^3\log m)\).

點擊查看代碼

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;

const int maxm = 3e2 + 10;
int m; ll l, a[maxm << 1], b[maxm << 1];
ll um, dm, sz, f[maxm * maxm << 1];

void add(ll w, ll v, int c) {
    if(w > 0) {
        for(int s = 1; c > 0; c -= s, s <<= 1) {
            int k = min(s, c);
            for(int i = sz; i >= k * w; i--) f[i] = max(f[i], f[i - k * w] + k * v);
        }
    }
    else {
        for(int s = 1; c > 0; c -= s, s <<= 1) {
            int k = min(s, c);
            for(int i = 0; i - k * w <= sz; i++) f[i] = max(f[i], f[i - k * w] + k * v);
        }
    }
}

int main() {
    ios :: sync_with_stdio(false); cin.tie(0); cout.tie(0);

    cin >> m >> l;
    for(int i = 0; i <= 2 * m; i++) {
        cin >> a[i], b[i] = a[i];
        if(i < m) dm += a[i] * (i - m);
        else um += a[i] * (i - m);
    }
    if(l < dm || l > um) cout << "impossible", exit(0);

    ll sum = um + dm, tmp;
    if(sum > l) {
        for(int i = 2 * m; i > m; i--) {
            tmp = sum - l;
            b[i] -= min(tmp / (i - m), a[i]);
            sum -= (i - m) * (a[i] - b[i]);
        }
    }
    else {
        for(int i = 0; i < m; i++) {
            tmp = l - sum;
            b[i] -= min(tmp / (m - i), a[i]);
            sum -= (i - m) * (a[i] - b[i]);
        }
    }

    sz = m * m << 1, tmp = sum - (l - m * m);
    memset(f, -0x3f3f, sizeof f); f[tmp] = 0;
    for(int i = 0; i <= 2 * m; i++) f[tmp] += b[i];
    for(int i = 0; i <= 2 * m; i++) {
        if(i == m) continue;
        if(b[i]) add(m - i, -1, min(b[i], sz));
        if(a[i] - b[i]) add(i - m, 1, min(a[i] - b[i], sz));
    }
    if(f[m * m] < 0) cout << "impossible";//m^2=tmp-sum+l
    else cout << f[m * m];

    return 0;
}

P4170 [CQOI2007] 涂色

一定程度上有貪心的感覺. 最優的涂色方案只會有兩種情況：分別涂無交的連續顏色段，或者涂相互包含的顏色段.

所以可以直接據此得到兩個轉移. 設 \(f_{i,j}\) 表示區間 \([i,j]\) 染色的最小步數，有：

\[f_{i,j}\leftarrow \min _{k=i}^{j-1}(f_{i,k}+f_{k+1,j}) \]

\[f_{i,j}\leftarrow \min_{c_i=c_j}(f_{i+1,j},f_{i,j-1}) \]

所有轉移取最小值，從小區間轉移到大區間. 時間復雜度 \(O(n^3)\).

回憶起之前 vp 到的另一個 DP，也是確定最優策略之后設計 DP 狀態和轉移：CF2115C.

P2135 方塊消除

很詭異的一個題.

首先正常的區間 DP 無法解決這個問題，因為直接拆成兩個區間來消除顯然不一定最優. 進一步地，我們希望在消除時欽定一種顏色與區間外的一些同色格子一起在消除完區間內其它格子后再消除.

一個看起來很對的 DP，設 \(f_{i,j,k}\) 表示消除區間 \([i,j]\) 并上后面 \(k\) 個與 \(j\) 同色的段的最大代價，\(k\) 個同色段是容易預處理的. 高高興興地寫出第一個轉移：

\[f_{i,j,k}\leftarrow f_{i,j-1,0}+w_{j,k} \]

我們還需要考慮一種可能是區間內有一個與 \(j\) 同色的段 \(k\)，先消除 \([k+1,j-1]\)，再消除 \([i,k]\) 與后面 \(j\) 與同色段的并. 然而我們的狀態無法處理不連續的同色段，所以必須改進.

考慮值域較小，我們可以直接把 \(k\) 改成同色格子數. 充分性顯然，考慮必要性，發現把一個完整段拆開不可能增加貢獻，所以在轉移過程中被優化掉了. 這其中蘊含著錯解不優的性質.

所以我們列出完整的轉移：

\[f_{i,j,k}\leftarrow f_{i,j-1,0}+(cnt_j+k)^2 \]

\[f_{i,j,k}\leftarrow \max_{l=i}^{j-2}[col_l=col_j](f_{i,l,k+cnt_j}+f_{k+1,j-1,0}) \]

轉移取最大值.

點擊查看代碼

#include<bits/stdc++.h>
using namespace std;

const int maxn = 60;
int n, col[maxn], cnt[maxn]; 
int suf[maxn], f[maxn][maxn][maxn * maxn << 1];

inline int pw(const int &x) {return x * x;}

int main() {
    ios :: sync_with_stdio(false); cin.tie(0); cout.tie(0);

    cin >> n; for(int i = 1; i <= n; i++) cin >> col[i];
    for(int i = 1; i <= n; i++) cin >> cnt[i];

    memset(f, -0x3f, sizeof f);
    for(int i = 1; i <= n; i++) for(int j = i + 1; j <= n; j++) if(col[i] == col[j]) suf[i] += cnt[j];
    for(int i = 1; i <= n; i++) for(int j = 0; j <= suf[i]; j++) f[i][i][j] = pw(cnt[i] + j);

    for(int len = 1; len <= n; len++) {
        for(int i = 1; i + len - 1 <= n; i++) {
            int j = i + len - 1;
            for(int k = 0; k <= suf[j]; k++) f[i][j][k] = max(f[i][j][k], f[i][j - 1][0] + pw(cnt[j] + k));
            for(int k = i; k < j - 1; k++) if(col[k] == col[j]) {
                for(int t = 0; t <= suf[j]; t++) f[i][j][t] = max(f[i][j][t], f[i][k][t + cnt[j]] + f[k + 1][j - 1][0]);
            }
        }
    } cout << f[1][n][0];

    return 0;
}

上述 DP 狀態的第三維可以看成是基于值域將顏色段選擇的狀態狀壓. 一個可能是，當段數限制在指數級別可以接受的數量級，而方塊數極大時，可能要使用狀壓下標來處理第三維狀態. 這時時間復雜度大概是 \(O(m^32^m)\)，好處是與值域無關了（）.

2025.10.24

P3174 [HAOI2009] 毛毛蟲

發現答案最終的形態一定是子樹內最大和次大毛毛蟲并起來，于是考慮 DP 求子樹內最大毛毛蟲. 毛毛蟲可以拆到每個點單獨貢獻，具體地，除了兩端貢獻為 \(d_u+1-1\)，其余點的貢獻為 \(d_u+1-2\).

如圖，減去原樹鏈上相鄰的點算重的貢獻.

令所有點的貢獻先減掉 \(fa_u\) 處重復的，在此基礎上再減去兒子處的并與 \(0\) 取 \(\max\)，即可實現貢獻的統計. 所以有轉移：

\[f_{u}=1+\max(0, d_u-[fa_u\neq -1]-1)+\max_{v\in son_u}f_v \]

考慮在每個點統計子樹內最大毛毛蟲和次大毛毛蟲并的最大值，維護類似于次短路，這里不再贅述. 合并時減去兩條毛毛蟲各算重的一個點的貢獻即可.

時間復雜度 \(O(n)\).

點擊查看代碼

#include<bits/stdc++.h>
using namespace std;

const int maxn = 3e5 + 10;
int n, m;
int ans, f[maxn];

vector<int> e[maxn];
void dfs(int u, int fa) {
    int mx1 = 0, mx2 = 0;
    for(int v : e[u]) {
        if(v == fa) continue; 
        dfs(v, u), f[u] = max(f[u], f[v]);
        if(f[v] > mx1) mx2 = mx1, mx1 = f[v];
        else if(f[v] > mx2) mx2 = f[v];
    }
    f[u] += 1 + max(0, (int)e[u].size() - (fa != -1) - 1);
    ans = max(ans, mx1 + mx2 + 1 + max(0, (int)e[u].size() - 2));
}

int main() {
    ios :: sync_with_stdio(false); cin.tie(0); cout.tie(0);

    cin >> n >> m; 
    for(int i = 1, u, v; i <= m; i++) cin >> u >> v, e[u].push_back(v), e[v].push_back(u);
    dfs(1, -1); cout << ans;

    return 0;
}

P3177 [HAOI2015] 樹上染色

要直接統計所有同色點對之間的距離之和是困難的，但是經過一條邊的點對數量是容易計算的，所以可以把貢獻拆到每條邊計算. 不妨認為初始時整個樹同色，DP 時對一些點染色. 設 \(f_{u,i}\) 表示子樹 \(u\) 內染 \(i\) 個點的最大貢獻. 有轉移：

\[f_{u,i}\leftarrow f_{u,i-j}+f_{v,j}+w_{u,v}\times \Big(j\times(k-j)+(sz_v-j)\times(n-k-sz_u-j)\Big) \]

轉移形如 \(0/1\) 背包，那么 \(i\) 當然應該從大到小枚舉. \(j\) 的枚舉涉及到一些邊界問題，當 \(j=0\) 時要用原來的 \(f_{u,i}\) 更新自己，但是如果從大到小枚舉，之前已經更新過 \(f_{u,i}\)，\(j=0\) 的更新就出現了錯誤. 解決方法可以在最開始先轉移 \(j=0\)，但是最好另開一個臨時數組來存，最后統一更新答案. 各種邊界問題在短時間搞明白并不容易. 在排除不合法的轉移之后，時間復雜度 \(O(n)\).

點擊查看代碼

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;

const int maxn = 2e3 + 10;
int n, k;

vector<array<int, 2> > e[maxn];

int sz[maxn]; ll f[maxn][maxn];
void dfs(int u, int fa) {
    sz[u] = 1;
    for(auto [v, w] : e[u]) {
        if(v == fa) continue;
        dfs(v, u), sz[u] += sz[v];
        for(int j = min(sz[u], k); j >= 0; j--) {
            for(int l = max(0, j - (sz[u] - sz[v])); l <= min(sz[v], j); l++) {//之前染過顏色的點個數上界是 sz[u]-sz[v]，可以推下界
                ll tmp = 1ll * l * (k - l) + 1ll * (sz[v] - l) * (n - k - (sz[v] - l));
                f[u][j] = max(f[u][j], f[u][j - l] + f[v][l] + tmp * w);
            }
        }
    }
}

int main() {
    ios :: sync_with_stdio(false); cin.tie(0); cout.tie(0);

    cin >> n >> k; k = min(k, n - k);
    for(int i = 1, u, v, w; i < n; i++) cin >> u >> v >> w, e[u].push_back({v, w}), e[v].push_back({u, w});
    dfs(1, -1); cout << f[1][k];

    return 0;
}

P3523 [POI 2011] DYN-Dynamite

讀錯題了qwq.

首先發現這個限制具有單調性，可以直接轉換成二分判斷可行性. 如果沒有 \(d_i\) 的限制是容易的，直接從葉子開始向上貪心地選即可：具體的，距離葉子為 \(mid\) 的先選擇，此后每距離 \(2\times mid\) 選擇一個點.

加上 \(d_i\) 的限制后考慮 DP. 根據上面的貪心，我們需要在狀態中記錄 \(u\) 到子樹中最遠的未被覆蓋的 \(d_i=1\) 的點 \(i\) 的距離，以及子樹內距離最近的被選擇 \(d_i=1\) 的點. 不妨設前者為 \(f_u\)，后者為 \(g_u\).

有基本的轉移：

\[f_u=\max_{v\in son_u}(f_u,f_v+1) \]

\[g_u=\min_{v\in son_u}(g_u,g_v+1) \]

根據題意，還有：

當 \(f_u+g_u\le mid\) 時，子樹 \(u\) 被完全覆蓋，令 \(f_u=-\infty\).
當 \(d_u=1\wedge g_u>mid\)，\(u\) 是未被覆蓋且可以選擇的點，有轉移 \(f_u\leftarrow\max(f_u,0)\).
當 \(f_u=mid\)，選擇最遠未被覆蓋的 \(d_i=1\) 的點 \(i\) 一定不劣，答案 \(+1\)，更新 \(f_u=-\infty,g_u=0\).

最后還需要特判根節點是否被覆蓋，否則答案額外 \(+1\). 時間復雜度 \(O(n)\).

點擊查看代碼

#include<bits/stdc++.h>
using namespace std;

const int maxn = 3e5 + 10, inff = 1e9;
int n, m; bool d[maxn];
int ans, cnt, f[maxn], g[maxn];

int mid;

vector<int> e[maxn];
void dfs(int u, int fa) {
    f[u] = -inff, g[u] = inff;
    for(int v : e[u]) {
        if(v == fa) continue;
        dfs(v, u);
        f[u] = max(f[u], f[v] + 1);
        g[u] = min(g[u], g[v] + 1);
    }
    if(f[u] + g[u] <= mid) f[u] = -inff;
    if(d[u] && g[u] > mid) f[u] = max(f[u], 0);
    if(f[u] == mid) f[u] = -inff, g[u] = 0, cnt++;
}

inline bool check() {
    cnt = 0, dfs(1, 0);
    if(f[1] >= 0) ++cnt;
    return cnt <= m;
}

int main() {
    ios :: sync_with_stdio(false); cin.tie(0); cout.tie(0);
    
    cin >> n >> m; for(int i = 1; i <= n; i++) cin >> d[i];
    for(int i = 1, u, v; i < n; i++) cin >> u >> v, e[u].push_back(v), e[v].push_back(u);
    
    int l = 0, r = n;
    while(l <= r) {
        mid = l + r >> 1;
        if(check()) ans = mid, r = mid - 1;
        else l = mid + 1;    
    } cout << ans;

    return 0;
}

posted @ 2025-10-22 21:45 Ydoc770 閱讀(10) 評論(1) 收藏舉報

刷新頁面返回頂部

2025.10.22

2025.10.23

2025.10.24

公告