整體概述

• 難度：1600 $\to$ 2200 $\to$ 2600

---

P6005 [USACO20JAN] Time is Mooney G

• 標簽：DP

• 前置知識：鏈式前向星

• 難度：綠 1600

題目描述：

輸入格式：

輸出格式：

樣例輸入：

3 3 1
0 10 20
1 2
2 3
3 1

樣例輸出：

24

解題思路：

• 發現數據范圍很小，考慮可否 $DP$。

• 定義 $d{p}_{i,j}$ 表示第 $i$ 天到達 $j$ 城市的最大收益，則單次更新可以暴力枚舉每個節點，更新其相鄰的節點，復雜度只為 $O(M)$。

  并且發現數據給定 $m_i\le 1000$，則 $T$ 不可能超過 $1000$ 否則 $c?T?T$ 一定大于總收益。所以總復雜度為 $O(1000?M)$。

完整代碼

#include<bits/stdc++.h>
#define Size(x) ((int)(x).size())
#define int long long
using namespace std;
const int N = 1e3+5,M = 2e3+5,INF = 0x3f3f3f3f;
int n,m,c,val[N],ha[N],idx;
struct Edge{int from,to,ne;}edge[M];
inline void ins(int u,int v){edge[++idx] = {u,v,ha[u]}, ha[u] = idx;
}
int dp[N][N];
signed main(){ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);cin >> n >> m >> c;for(int i=1;i<=n;i++) cin >> val[i];for(int i=1,u,v;i<=m;i++){cin >> u >> v;ins(u,v);}for(int i=0;i<N;i++) for(int j=0;j<N;j++) dp[i][j] = -INF;dp[0][1] = 0;int ans = 0;for(int t=0;t<=1000;t++){for(int u=1;u<=n;u++){if(dp[t][u]==-INF) continue;for(int i=ha[u];i;i=edge[i].ne){int v = edge[i].to;dp[t+1][v] = max(dp[t+1][v],dp[t][u]+val[v]);}}ans = max(ans,dp[t][1] - c*t*t);}cout << ans;return 0;
}

---

P10391 [藍橋杯 2024 省 A] 零食采購

• 標簽：重鏈剖分

• 前置知識：線段樹、狀態壓縮

• 難度：藍 2200

題目描述：

輸入格式：

輸出格式：

樣例輸入：

4 2
1 2 3 1
1 2
1 3
2 4
4 3
1 4

樣例輸出：

3
2

解題思路：

• 題目很簡單，給出一棵樹，每個節點有一個權值 $1\le c\le 20$，大量查詢每次詢問兩個節點 $u$，$v$ 在樹上簡單路徑上經過的所有店的權值類型個數。

• 我們發現 $c$ 很小，可以壓縮到 $int$ 的每一個位上，那么原問題轉化為詢問樹上簡單路徑上的權值的 或和，那么就是裸的重鏈剖分的板子題了，線段樹只需要支持單點修改，區間查 或和 即可。

完整代碼

#include<bits/stdc++.h>
#define Size(x) ((int)(x).size())
#define int long long
using namespace std;
const int N = 1e5+5;
int n,q,ha[N],idx,a[N];
struct Edge{int to,ne;}edge[N<<1];
inline void ins(int u,int v){edge[++idx]={v,ha[u]}, ha[u] = idx;
}
int fa[N],siz[N],son[N],dep[N];
inline void dfs1(int u,int par){fa[u] = par, dep[u] = dep[par]+1;siz[u] = 1;for(int i=ha[u];i;i=edge[i].ne){int v = edge[i].to;if(v == par) continue;dfs1(v,u), siz[u] += siz[v];if(siz[son[u]] < siz[v]) son[u] = v;}
}
int dfn[N],back[N],Time,top[N];
inline void dfs2(int u,int Top){top[u] = Top;dfn[u] = ++Time, back[Time] = u;if(!son[u]) return;dfs2(son[u],Top);for(int i=ha[u];i;i=edge[i].ne){int v = edge[i].to;if(v != fa[u] && v != son[u]) dfs2(v,v);}
}
#define ls ((u)<<1)
#define rs ((u)<<1|1)
#define mid (((l)+(r))>>1)
int tr[N<<2];
inline void up(int u){tr[u] = tr[ls] | tr[rs];
}
inline void build(int l,int r,int u){if(l == r){tr[u] = 1<<a[back[l]];return ;}build(l,mid,ls), build(mid+1,r,rs);up(u);
}
inline int queryOR(int x,int y,int l=1,int r=n,int u=1){if(x <= l && r <= y) return tr[u];int ans = 0;if(x <= mid) ans |= queryOR(x,y,l,mid,ls);if(y > mid) ans |= queryOR(x,y,mid+1,r,rs);return ans;
}
inline int query(int u,int v){int ans = 0;while(top[u] != top[v]){if(dep[top[u]] < dep[top[v]]) swap(u,v);ans |= queryOR(dfn[top[u]],dfn[u]);u = fa[top[u]];}if(dep[u] < dep[v]) swap(u,v);ans |= queryOR(dfn[v],dfn[u]);return ans;
}
signed main(){ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);cin >> n >> q;for(int i=1;i<=n;i++) cin >> a[i];for(int i=1,u,v;i<n;i++){cin >> u >> v;ins(u,v), ins(v,u);}dfs1(1,0);dfs2(1,1);build(1,n,1);while(q--){ int u,v; cin >> u >> v;int res = query(u,v), cnt = 0;while(res) res &= res-1, cnt += 1;cout << cnt << '\n';} return 0;
}

---

P7519 [省選聯考 2021 A/B 卷] 滾榜

• 標簽：狀壓DP

• 前置知識：差分數組

• 難度：紫 2600

題目描述：

輸入格式：

輸出格式：

樣例輸入：

3 6
1 2 1

6 50
4 7 9 3 0 3

11 300
6 8 8 12 0 11 6 1 0 15 5

樣例輸出：

5

96

30140983

解題思路：

• 發現題目的數據范圍很小，求總排名方案書，肯定為狀壓 $DP$。

• 狀壓 $DP$ 肯定有一維 $O(2^n)$ 表示已經公布了哪幾個人，本題的 $b_i$ 要求單調不降，肯定需要一維 $O(n)$ 記錄上公布的人，需要一維 $O(m)$ 記錄已經用了多少道題。

  接著考慮如何轉移，對于每個狀態 $s$，枚舉最后一個人是 $i$，暴力枚舉下一個人是 $j$，假設 $i$ 要變成第一所需的過題數為 $d$，那么由于 $b_i$ 需要單調不降，后續所有的人都需要過 $d$ 到題，所以轉移需要消耗 $cnt?d$ 道題，其中 $cnt$ 為還沒有被公布的人數。

• 最后暴力統計所有答案即可，總復雜度 $O(2^n·n2·m)。

• 我們可以預處理一個數組 $s_i$ 表示 $i$ 超過所有人所需的最小的 $b_i$，再預處理一個數組 $cn{t}_i$ 表示狀態為 $i$ 時還沒有公布的人數為 $cn{t}_i$，那么便可以很方便地轉移了。

完整代碼

#include<bits/stdc++.h>
using namespace std;
const int N = 13, M = 505;
int n,m,up,dp[1<<N][N][M],a[N],d[N][N],s[N],cnt[1<<N];
signed main(){ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);cin >> n >> m; up = 1<<n;for(int i=0;i<n;i++) cin >> a[i];for(int i=0;i<n;i++) for(int j=0;j<n;j++){if(j < i) d[i][j] = max(0,a[j]-a[i]+1);else d[i][j] = max(0,a[j]-a[i]);}for(int i=0;i<n;i++) for(int j=0;j<n;j++) s[i] = max(s[i],d[i][j]);cnt[0] = n;for(int i=1;i<up;i++) cnt[i] = cnt[i>>1] - (i&1);for(int i=0;i<n;i++) if(n*s[i] <= m) dp[1<<i][i][n*s[i]] = 1;for(int s=0;s<up;s++){for(int i=0;i<n;i++) if((s>>i)&1){for(int j=0;j<n;j++) if(!((s>>j)&1)){for(int t=d[j][i]*cnt[s];t<=m;t++){dp[s|(1<<j)][j][t] += dp[s][i][t-d[j][i]*cnt[s]];}}}}long long ans = 0;for(int i=0;i<n;i++) for(int j=1;j<=m;j++) ans += dp[up-1][i][j];cout << ans;return 0;
}