E. Move and Swap

Heltion
由于紅色硬幣向下一層走的時候只能走兒子，而藍色無限制（對后續操作無影響），于是考慮下面表示

狀態表示：$f_u$表示當前是紅色硬幣，向下一層走后的最大價值。
狀態轉移：
假設下一步走到兒子$v$，并且不交換，也就是$v$是紅色硬幣，存在轉移$f_u=f_v+|a_v?a_m|$，$m$表示與$v$同層的那些節點

如果交換，那么$v$就是藍色硬幣，需要找到一個與$v$同層的節點$m$（作為紅色）存在轉移$f_u=f_m+|a_v?a_m|$

去掉絕對值，預處理一些東西輔助轉移即可（$v\to u$）我為人人轉移

#define IO ios::sync_with_stdio(false);cin.tie(nullptr);cout.tie(nullptr) #pragma GCC optimize(2) #include<cstring> #include<iostream> #include<algorithm> using namespace std; using ll=long long; constexpr int N=200010; constexpr ll INF=0x3f3f3f3f3f3f3f3f; int h[N],e[2*N],ne[2*N],idx; void add(int a,int b){e[idx]=b,ne[idx]=h[a],h[a]=idx++;} int d[N]; ll a[N]; vector<int> g[N]; ll f[N]; int fa[N],n; void dfs_d(int u) {d[u]=d[fa[u]]+1;for(int i=h[u];i!=-1;i=ne[i]){int j=e[i];if(j==fa[u]) continue;fa[j]=u;dfs_d(j);} } void bfs(int S) {for(int i=S;i>1;i--){// 不交換顏色u由兒子v轉移ll vmin=INF,vmax=-INF;for(int v:g[i]) vmin=min(vmin,a[v]),vmax=max(vmax,a[v]);for(int v:g[i]){int u=fa[v];f[u]=max(f[u],max(a[v]-vmin,vmax-a[v])+f[v]);}// 交換顏色由同層節點轉移ll p1=-INF,p2=-INF;for(int v:g[i]) p1=max(p1,f[v]+a[v]),p2=max(p2,f[v]-a[v]);for(int v:g[i]){int u=fa[v];f[u]=max(f[u],p1-a[v]);f[u]=max(f[u],p2+a[v]);} } } void init(int n) {memset(h,-1,(n+1)*sizeof(int));idx=0;memset(d,0,(n+1)*sizeof(int));memset(fa,0,(n+1)*sizeof(int));memset(f,0,(n+1)*sizeof(ll));for(int i=0;i<=n;i++) g[i].clear(); } int main() {IO;int T=1;cin>>T;while(T--){cin>>n;init(n);for(int i=2;i<=n;i++){int v;cin>>v;add(v,i),add(i,v);}for(int i=2;i<=n;i++) cin>>a[i];dfs_d(1);for(int i=1;i<=n;i++) g[d[i]].push_back(i);bfs(*max_element(d+1,d+1+n));cout<<f[1]<<'\n';}return 0; }

寫的時候狀態定義不好，導致不容易轉移，以后狀態定義明確后在下手！

總結

以上是生活随笔為你收集整理的codeforces1485 E. Move and Swap（dp）的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。