DP 選做（長(zhǎng)期更新）

在做這個(gè)題單：https://www.luogu.com.cn/training/629645
題目按照獵奇程度排序.

CF1016F Road Projects

Hint：抽出 \(1\sim n\) 的鏈 \(L\) 之后鏈上每個(gè)節(jié)點(diǎn)有一棵子樹，考慮根據(jù)子樹的狀態(tài)分討，對(duì)子樹進(jìn)行處理.

要使最短路最長(zhǎng)，但是原先的最短路無(wú)法變動(dòng). 所以最短路在加一條邊發(fā)生改變當(dāng)且僅當(dāng)出現(xiàn)了一條新的最短路徑，并且這條最短路是所有可能新路徑中最長(zhǎng)的一條.

不必構(gòu)造新的最短路，只需要存在一個(gè)子樹大小大于 \(2\)，連接子樹中未直接相連的兩點(diǎn)即可.
需要構(gòu)造新的最短路，最短路一定是由兩個(gè)子樹到根距離最長(zhǎng)的點(diǎn)相連，且每次詢問(wèn)都連接的是相同的兩個(gè)點(diǎn). 設(shè)子樹 \(u\) 中到 \(u\) 最長(zhǎng)距離為 \(f_u\)，鏈上每個(gè)點(diǎn)到起點(diǎn)的距離為 \(dis_u\)，這些可以簡(jiǎn)單預(yù)處理. 有轉(zhuǎn)移：

\[ans\leftarrow \max_{u\neq v\ u,v\in L}\Big(dis_u+f_u+f_v+dis_n-(dis_v)\Big) \]

拿個(gè)變量存一下前綴最大的 \(dis_u+f_u\) 即可做到線性，當(dāng)然也可以畫蛇添足使用單調(diào)棧.

詢問(wèn)根據(jù)上面的分討，也可以做到線性. 總復(fù)雜度 \(O(n+q)\).

點(diǎn)擊查看代碼

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

constexpr int maxn = 3e5 + 10;
int n, m;

int tot, head[maxn];
struct edge{int nxt, v, w;} e[maxn << 1];
inline void add(int u, int v, int w) {e[++tot] = {head[u], v, w}, head[u] = tot; return;}

int tp, s[maxn], val[maxn];
bool vis[maxn];
bool dfs1(int u, int fa) {
    if(u == n) return true;
    for(int i = head[u]; i; i = e[i].nxt) {
        int v = e[i].v, w = e[i].w; if(v == fa) continue;
        s[++tp] = v, val[tp] = w, vis[v] = true; 
        if(dfs1(v, u)) return true;
        tp--, vis[v] = false;
    } return false;
}
int sz[maxn]; ll f[maxn];
void dfs2(int u, int fa) {
    sz[u] = 1;
    for(int i = head[u]; i; i = e[i].nxt) {
        int v = e[i].v, w = e[i].w; if(v == fa || vis[v]) continue;
        dfs2(v, u); sz[u] += sz[v], f[u] = max(f[v] + w, f[u]);
    }
}

ll ans, dis[maxn]; int r, q[maxn];
int main() {
    ios :: sync_with_stdio(false); cin.tie(0); cout.tie(0);

    cin >> n >> m; bool tag_sz = false;
    for(int i = 1, u, v, w; i < n; i++) cin >> u >> v >> w, add(u, v, w), add(v, u, w);
    s[tp = 1] = 1, vis[1] = true; dfs1(1, 0); 
    for(int i = 2; i <= tp; i++) dis[i] = dis[i - 1] + val[i];
    for(int i = 1; i <= tp; i++) dfs2(s[i], 0), tag_sz |= (sz[s[i]] > 2);
    if(sz[s[1]] > 1 || sz[s[2]] > 1) ans = max(ans, f[s[1]] + f[s[2]] + dis[tp] - dis[2]);
	q[r = 1] = 1;
	for(int i = 3; i <= tp; i++){
		ans = max(ans, f[s[i]] + f[s[q[1]]] + dis[q[1]] + dis[tp] - dis[i]);
		if(sz[s[i]] > 1 || sz[s[i - 1]] > 1) ans = max(ans, f[s[i]] + f[s[i - 1]] + dis[tp] - dis[i] + dis[i - 1]);
		while(r && f[s[i - 1]] + dis[i - 1] >= f[s[q[r]]] + dis[q[r]]) r--;
		q[++r] = i - 1;
	}
    for(int i = 1; i <= m; i++) {
        ll x; cin >> x;
        cout << (tag_sz ? dis[tp] : min(dis[tp], ans + x)) << endl;
    }
    return 0;
}

P3188 [HNOI2007] 夢(mèng)幻島寶珠

Hint：拆成題目所給的形式，對(duì)容量狀壓.

題目本身只是一個(gè)裸的 \(01\) 背包，但是數(shù)據(jù)范圍奇大無(wú)比，所以肯定不能直接做了.

數(shù)據(jù)范圍保證了每個(gè) \(w_i\) 可以拆成 \(a\times 2^b\) 的形式，這啟發(fā)我們對(duì)于每個(gè) \(w_i\) 把 \(a_i\) 和 \(b_i\) 拆出來(lái)，考慮用這兩個(gè)參數(shù)來(lái)刻畫有關(guān) \(w\) 的轉(zhuǎn)移.

考慮狀壓，設(shè) \(f_{i,j}\) 表示重量為 \(j\times 2^i\) 時(shí)的最大價(jià)值. 觀察到 \(i\) 相同時(shí)可以直接轉(zhuǎn)移：

\[f_{i,j}=\max_{b_k=i}(f_{i,j},f_{i,j-a_k}) \]

考慮不同的 \(i\) 怎么合并. 如果給 \(i-1\) 分 \(k\times2^{i}\) 的重量，也就是 \((2k)\times2^{i-1}\)，相當(dāng)于 \(j\) 這一維有 \(2k\) 的可分配重量. 同時(shí)由于總價(jià)值 \(W\) 拆成二進(jìn)制也可能有 \(2^{i-1}\) 的貢獻(xiàn)，如果有也一并加上. 就有轉(zhuǎn)移：

\[f_{i,j}=\max_{k=0}^j(f_{i-1,2k+((W>>(i-1))\&1)}+f_{i,j-k}) \]

點(diǎn)擊查看代碼

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

const int maxn = 1e2 + 10, maxw = 1e3 + 10;
int n, W, w[maxn], v[maxn];
int maxb, wa[maxn], wb[maxn];
ll f[40][maxw];//n個(gè)物品容量為a，容量上界為n*a

void solve() {
    for(int i = 1; i <= n; i++) cin >> w[i] >> v[i];
    for(int i = 1; i <= n; i++) {
        for(int b = 1; ; b++) if(w[i] % (1ll << b) != 0) {wb[i] = --b; break;}
        wa[i] = w[i] / (1 << wb[i]);
    }
    
    for(int i = 1; i <= n; i++) 
        for(int a = 1000; a >= wa[i]; a--) 
            f[wb[i]][a] = max(f[wb[i]][a], f[wb[i]][a - wa[i]] + v[i]);
    maxb = 0;
    for(int s = (W >> 1); s; s >>= 1) maxb++;
    for(int b = 1; b <= maxb; b++) {
        for(int a = 1000; a >= 0; a--) {
            for(int k = 0; k <= a; k++) {
                f[b][a] = max(f[b][a], f[b][a - k] + f[b - 1][min(1000, (k << 1) + ((W & (1 << (b - 1))) != 0))]);
            }
        }
    } cout << f[maxb][1] << endl;

    return;
}
void cln() {memset(f, 0, sizeof f); return;}

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

    while(1) {
        cin >> n >> W; if(n == -1) break;
        solve(), cln();
    }

    return 0;
}

AT_arc107_d [ARC107D] Number of Multisets

Hint：類似于經(jīng)典自然根號(hào)分拆數(shù)的做法，考慮添加一個(gè) \(1\)，或者所有數(shù)乘 \(1\over 2\) 即可構(gòu)造出所有可能的可重集.

設(shè) \(f_{i,j}\) 表示當(dāng)前 \(i\) 個(gè)元素和為 \(j\) 的方案數(shù)，有轉(zhuǎn)移：

\[f_{i,j}=f_{i-1,j-1}+f_{i,2\times j} \]

時(shí)間復(fù)雜度 \(O(n^2)\).右式后者類似于完全背包，可以乘若干個(gè) \(1\over2\)，所以第一維是 \(i\).

點(diǎn)擊查看代碼

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

constexpr int maxn = 3e3 + 10, mo = 998244353;
int n, k, f[maxn][maxn];

inline int add(const int &x, const int &y) {return x + y >= mo ? x + y - mo : (x + y < 0 ? x + y + mo : x + y);}
inline void upd(int &x, const int &y) {return x = add(x, y), void(0);}

int main() {
    cin >> n >> k;
    f[0][0] = 1;
    for(int i = 1; i <= n; i++) {
        for(int j = i; j >= 0; j--) {
            if(j * 2 <= i) upd(f[i][j], f[i][j * 2]);
            upd(f[i][j], f[i - 1][j - 1]);
        }
    }
    cout << f[n][k];
    return 0;
}

題意似乎可以轉(zhuǎn)化為 \(n\) 恰好拆分成 \(k\) 個(gè)數(shù)的和的方案數(shù)，有更加高效的多項(xiàng)式優(yōu)化做法.

CF1485F Copy or Prefix Sum

Hint：題目第二個(gè)條件需要在狀態(tài)里面記錄前綴和，考慮怎么優(yōu)化轉(zhuǎn)移.

設(shè) \(f_{i,j}\) 表示考慮前 \(i\) 個(gè)數(shù)，前綴和為 \(j\) 的方案數(shù)，有轉(zhuǎn)移：

\[f_{i,j}=f_{i-1,j-b_i}+\sum_xf_{i-1,x} \]

由于 \(a_i\) 沒(méi)有限制數(shù)據(jù)范圍，所以一切 \(f_{i-1,x}\) 都可以轉(zhuǎn)移過(guò)來(lái).

狀態(tài)第一維可以壓掉；第二維要么相當(dāng)于整體下標(biāo)平移，要么是整體求和，所以可以拿個(gè)變量存一下.

代碼實(shí)現(xiàn)開一個(gè) map 來(lái)存 \(f\) 的值域維，記一個(gè) sum 表示總和，記一個(gè) res 表示下標(biāo)偏移總量，整體 DP 即可.

點(diǎn)擊查看代碼

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

constexpr int maxn = 3e3 + 10, mo = 1e9 + 7;
int T, n;

inline int add(const int &x, const int &y) {return x + y >= mo ? x + y - mo : (x + y < 0 ? x + y + mo : x + y);}
inline void upd(int &x, const int &y) {return x = add(x, y), void(0);}

map<ll, int> f;
void solve() {
    cin >> n; int x = 0, sum = 0; ll res = 0; map<ll, int>().swap(f);

    sum = f[0] = 1;
    for(int i = 1; i <= n; i++) {
        cin >> x; int val = add(sum, -f[res]); 
        f[res] = sum; upd(sum, val), res -= x;
    } cout << sum << endl;
    return;
}

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

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

    return 0;
}

CF1485E Move and Swap

Hint：不難發(fā)現(xiàn)每次紅藍(lán)都會(huì)往下走，考察更加固定的紅點(diǎn)，每次交換/不交換分討，從上一層或父親轉(zhuǎn)移過(guò)來(lái).

不交換時(shí)，\(u\) 從 \(fa_u\) 轉(zhuǎn)移過(guò)來(lái)，顯然有一個(gè)貪心是藍(lán)點(diǎn)最優(yōu)只可能在這一層的最大或最小值，預(yù)處理一下即可.
交換后，紅點(diǎn)可以任意選擇位置，考慮此時(shí)藍(lán)點(diǎn)代替原先紅點(diǎn)由父親轉(zhuǎn)移到兒子的最大/最小值，于是同樣可以預(yù)處理求得. 實(shí)現(xiàn)時(shí)可以把絕對(duì)值去掉維護(hù)兩個(gè)變量.

點(diǎn)擊查看代碼

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

constexpr int maxn = 2e5 + 10, inff = 1e9 + 1;
int T, n, a[maxn];

int tot, head[maxn];
struct edge{int nxt, v;} e[maxn << 1];
inline void add(int u, int v) {e[++tot] = {head[u], v}, head[u] = tot; return;}

int dep[maxn], fa[maxn], mx[maxn], mi[maxn];
vector<int> E[maxn];
void dfs(int u, int f) {
    dep[u] = dep[f] + 1, fa[u] = f;
    E[dep[u]].push_back(u);
    mi[dep[u]] = min(mi[dep[u]], a[u]), mx[dep[u]] = max(mx[dep[u]], a[u]);
    for(int i = head[u], v; i; i = e[i].nxt) {
        v = e[i].v; if(v == f) continue;
        dfs(v, u);
    } return;
}
ll ans, f[maxn], mxf[maxn], mif[maxn]; bool vis[maxn];

void solve() {
    ans = tot = 0; cin >> n; 
    for(int i = 1; i <= n; i++) mx[i] = vis[i] = head[i] = f[i] = 0, vector<int>().swap(E[i]), mi[i] = inff;
    
    for(int i = 2, v; i <= n; i++) cin >> v, add(i, v), add(v, i);
    for(int i = 2; i <= n; i++) cin >> a[i];
    dfs(1, 0);

    for(int i = 2; i <= n; i++) {
        ll v1 = -inff, v2 = -inff;
        for(int u : E[i]) v1 = max(v1, f[fa[u]] + a[u]), v2 = max(v2, f[fa[u]] - a[u]);
        for(int u : E[i]) {
            f[u] = max(f[u], f[fa[u]] + max(mx[i] - a[u], a[u] - mi[i]));
            f[u] = max(f[u], max(v1 - a[u], v2 + a[u]));
            ans = max(f[u], ans);
        }
    }
    cout << ans << endl;

    return;
}

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

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

    return 0;
}

CF1292C Xenon's Attack on the Gangs

Hint：對(duì)貢獻(xiàn)反演，拆成至少包含 \(0\sim k-1\) 的路徑條數(shù)，貪心地填數(shù).

\[\begin{aligned} ans&=\sum_{1\le u< v\le n}\text{mex}(u, v)\\ &=\sum_{k=1}^n\left(\sum_{\text{mex}(u,v)=k}k\right)\\ &=\sum_{k=1}^n\left(\sum_{\text{mex}(u,v)\ge k}1\right)\\ \end{aligned} \]

于是考慮貪心地填數(shù)使得路徑數(shù)最大. 容易發(fā)現(xiàn)只有所有包含 \(0\) 的路徑可能有貢獻(xiàn)，所以 \(1\) 應(yīng)該填在與 \(0\) 相鄰的位置，同理 \(2\) 應(yīng)該填在 \(0,1\) 所在路徑的相鄰位置. 每次我們的當(dāng)前路徑會(huì)向左或向右延伸，造成的貢獻(xiàn)就是左右兩個(gè)子樹的 \(size\) 之積. 具體地，對(duì)于路徑 \(u,v\)，貢獻(xiàn)實(shí)際上是以 \(u\) 為根，子樹 \(v\) 的 \(size\) 與以 \(v\) 為根，子樹 \(u\) 的 \(size\). 不妨記作 \(size_{rt, i}\)，容易在 \(O(n^2)\) 預(yù)處理出來(lái)，并順便求出以 \(rt\) 為根的父親 \(fa_{rt,i}\).

設(shè) \(f_{u,v}\) 為填了鏈 \((u,v)\) 的最大路徑數(shù)，不難得到轉(zhuǎn)移：

\[f_{u,v} = sz_{u,v}\times size_{v, u} + \max\left(f_{u,fa_{u,v}},f_{fa_{v,u},v}\right) \]

記憶化搜索即可通過(guò)，時(shí)間復(fù)雜度 \(O(n^2)\).

點(diǎn)擊查看代碼

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

const int maxn = 3e3 + 10;
int n, rt;

int tot, head[maxn];
struct edge{int nxt, v;} e[maxn << 1];
inline void add(int u, int v) {e[++tot] = {head[u], v}, head[u] = tot; return;}

int sz[maxn][maxn], fa[maxn][maxn];
void dfs0(int u, int f) {
    fa[rt][u] = f, sz[rt][u] = 1;
    for(int i = head[u], v; i; i = e[i].nxt) {
        v = e[i].v; if(v == f) continue;
        dfs0(v, u); sz[rt][u] += sz[rt][v];
    } return;
}
ll ans, f[maxn][maxn];
ll dp(int u, int v) {
    if(u == v) return 0;
    if(f[u][v]) return f[u][v];
    return f[u][v] = max(dp(u, fa[u][v]), dp(fa[v][u], v)) + sz[u][v] * sz[v][u];
}


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

    cin >> n;
    for(int i = 1, u, v; i < n; i++) cin >> u >> v, add(u, v), add(v, u);
    for(rt = 1; rt <= n; rt++) dfs0(rt, 0);

    for(int u = 1; u <= n; u++) for(int v = 1; v <= n; v++) ans = max(ans, dp(u, v));
    cout << ans;

    return 0;
}

P6669 [清華集訓(xùn) 2016] 組合數(shù)問(wèn)題

Hint：Locus 定理轉(zhuǎn)換成數(shù)位 DP.

似乎在遠(yuǎn)古校測(cè)中見過(guò)一樣的處理思路. 考慮縮小組合數(shù)的范圍，用 Locus 定理進(jìn)行拆分：

\[{n\choose m}\equiv{{\lfloor{n\over k}\rfloor}\choose \lfloor{m\over k}\rfloor}{n\bmod k\choose m\bmod k}\pmod k \]

遞歸展開右式，得到的式子就是 \(n,m\) 在 \(k\) 進(jìn)制下每一位組合數(shù)之積. 由于每一項(xiàng)都小于 \(k\) 了，所以成立當(dāng)且僅當(dāng)右式為 \(0\)，也就是組合數(shù)存在一項(xiàng)下面大于上面的. 根據(jù)這個(gè)性質(zhì)直接數(shù)位 DP 即可.

點(diǎn)擊查看代碼

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

constexpr int mo = 1e9 + 7;
int t; ll k, n, m;

int la, lb;
int a[70], b[70], f[70][2][2][2][2];

inline int add(const int &x, const int &y) {return x + y >= mo ? x + y - mo : x + y;}
inline void upd(int &x, const int &y) {return x = add(x, y), void(0);}

int dp(int t, bool ok, bool dif, bool lima, bool limb) {
    if(!t) return ok;
    if(f[t][ok][dif][lima][limb] != -1) return f[t][ok][dif][lima][limb];
    
    int res = 0;
    int upa = lima ? k - 1 : a[t], upb = limb ? k - 1 : b[t];
    for(int i = 0; i <= upa; i++) for(int j = 0; (j <= i || dif) && j <= upb; j++) {
        upd(res, dp(t - 1, ok | (i < j), dif | (i != j), lima | (i < upa), limb | (j < upb)));
    } return f[t][ok][dif][lima][limb] = res;
}

void init() {la = lb = 0, memset(f, -1, sizeof f), memset(a, 0, sizeof a), memset(b, 0, sizeof b);}
void solve() {
    cin >> n >> m; init();
    while(n) a[++la] = n % k, n /= k;
    while(m) b[++lb] = m % k, m /= k;

    cout << dp(max(la, lb), 0, 0, 0, 0) << endl;
    return;
}

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

    cin >> t >> k;
    while(t--) solve();

    return 0;
}

posted @ 2025-09-07 18:02 Ydoc770 閱讀(14) 評(píng)論(0) 收藏舉報(bào)

刷新頁(yè)面返回頂部

公告