Monster Hunter(2020南京M)

題意：

給你一顆樹，樹上每個節點都是一個hpi 血量的怪物。打敗每個怪物所需要的能量值為hpi + 所 有 存 活 的 直 接 子 節 點 的 hpj 。每次必須要消滅父節點后才能消滅子節點。此外你還有m個魔咒，每個魔咒可以不耗費能量且可以消滅任意一個存活的怪物（無論其父親節點是否存在）。問你m=0，1，2，3…，n時的最低總能量花費分別為多少。

題解：

不難看出樹形dp
那我們可以設狀態為：dp[i][j]:表示i的子樹還剩j個點的最小花費(其他i-j相當于用魔咒消滅)
我們現在可以考慮轉移，發現不好轉移，因為這個子樹根節點第i個點也有可能被刪除，所以我們再加一維，dp[i][j][0/1]:表示i的子樹還剩j個點的最小花費，且第i個點是否被消滅(0表示被消滅，1表示未消滅)
這樣就可以轉移了：
u是v的父親節點，用v更新u
可以得到轉移方程：

for(int i=siz[u];i>=0;i--){for(int j=0;j<=min(i,siz[v]);j++){dp[u][i][0]=min(dp[u][i][0],dp[u][i-j][0]+dp[v][j][1]);//u不保存，v保存dp[u][i][0]=min(dp[u][i][0],dp[u][i-j][0]+dp[v][j][0]);//dp[u][i][1]=min(dp[u][i][1],dp[u][i-j][1]+dp[v][j][0]);//dp[u][i][1]=min(dp[u][i][1],dp[u][i-j][1]+dp[v][j][1]+hp[v]);// u，v都保存時要算上v的hp值} }

就是分別討論u和v是0，1的情況，一共四個情況，分別更新
這樣能過81.58%的數據，T了

我們分析一下復雜度，相當于用以u為根的子樹中所有點，與以v為根的子樹中所有點兩兩匹配，這樣會有重復，因為以v為根的子樹也在以u為根的子樹里，這樣會重復計算siz[v]部分。這樣的話，重復計算部分有${\sum }_{i=1}^{n}siz[i]$,鐵超時，總復雜度是$(2n^2)$(隊友說的，等會證明再更新),會被卡常

---

如何可以避免重復部分？我們改變寫法，將dp[i]=dp[i-j]+dp[j]改為dp[i+j]=dp[i]+dp[j]，i枚舉的是以u為根的子樹，除以v為根的子樹之外的節點，j枚舉的是以v為根的子樹的節點，這樣枚舉，恰好使得任意兩點被枚舉到，不會多，不會漏，這樣是$O(n^2)$
圖片出處

代碼：

#include <bits/stdc++.h> #include <unordered_map> #define debug(a, b) printf("%s = %d\n", a, b); using namespace std; typedef long long ll; typedef unsigned long long ull; typedef pair<int, int> PII; clock_t startTime, endTime; //Fe~Jozky const ll INF_ll= 1e18; const int INF_int= 0x3f3f3f3f; void read(){}; template <typename _Tp, typename... _Tps> void read(_Tp& x, _Tps&... Ar) {x= 0;char c= getchar();bool flag= 0;while (c < '0' || c > '9')flag|= (c == '-'), c= getchar();while (c >= '0' && c <= '9')x= (x << 3) + (x << 1) + (c ^ 48), c= getchar();if (flag)x= -x;read(Ar...); } template <typename T> inline void write(T x) {if (x < 0) {x= ~(x - 1);putchar('-');}if (x > 9)write(x / 10);putchar(x % 10 + '0'); } void rd_test() { #ifdef ONLINE_JUDGE #elsestartTime = clock ();freopen("data.in", "r", stdin); #endif } void Time_test() { #ifdef ONLINE_JUDGE #elseendTime= clock();printf("\nRun Time:%lfs\n", (double)(endTime - startTime) / CLOCKS_PER_SEC); #endif } #define int long long int n; const int maxn=2e3+9; vector<int>vec[maxn]; int hp[maxn]; int dp[maxn][maxn][2]; int siz[maxn]; void dfs(int u,int fa){dp[u][0][0]=0;dp[u][1][1]=hp[u];for(auto v:vec[u]){dfs(v,u);for(int i=siz[u]-siz[v];i>=0;i--){for(int j=0;j<=siz[v];j++){dp[u][i+j][0]=min(dp[u][i+j][0],dp[u][i][0]+dp[v][j][1]);//u不保存，v保存 dp[u][i+j][0]=min(dp[u][i+j][0],dp[u][i][0]+dp[v][j][0]);//dp[u][i+j][1]=min(dp[u][i+j][1],dp[u][i][1]+dp[v][j][0]);//dp[u][i+j][1]=min(dp[u][i+j][1],dp[u][i][1]+dp[v][j][1]+hp[v]);// u，v都保存時要算上v的hp值 // dp[u][i][2]=dp[u][i-j][1]+dp[v][j][w]+(w==0?0:w[v])//}}} } void dfs1(int u,int fa){siz[u]=1;for(auto v:vec[u]){if(v==fa)continue;dfs1(v,u);siz[u]+=siz[v]; } } void solve(){read(n);for(int i=0;i<=n;i++){for(int j=0;j<=n;j++){dp[i][j][0]=dp[i][j][1]=1e18;}}for(int i=1;i<=n;i++)vec[i].clear();for(int i=2;i<=n;i++){int u;read(u);vec[u].push_back(i);}for(int i=1;i<=n;i++){read(hp[i]);}dfs1(1,0);dfs(1,0);for(int i=0;i<=n;i++){printf("%lld ",min(dp[1][n-i][0],dp[1][n-i][1]));}printf("\n"); } signed main() {rd_test();int t;read(t);while(t--){solve();}//Time_test(); }

總結

以上是生活随笔為你收集整理的Monster Hunter(2020南京M)的全部內容，希望文章能夠幫你解決所遇到的問題。

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