PRoblem: 給一棵樹，問最少砍多少刀就可以劃分出來一個p個節點的子樹。 Solution: 對于一個根節點i，我們定義這個i一定在最終劃分出來的子樹當中，dp[i][k]表示以i為根節點的子樹劃分出k個節點所需要的最少次數。那么dp[i][j+k] = min(dp[i][j+k], dp[i][j]+dp[son[i]][k]-1)。這個狀態轉換理解為：對于i為根節點的這顆子樹，需要劃分出來j+k個節點，那么我們可以從這個兒子中劃分出來k個，從其它部分劃分出來j個，-1是因為要把兒子那部分合并進來，就需要減一刀。最終動規完畢后，需要再遍歷一遍所有節點，找到以哪個節點為根節點的子樹才是最優解，而最后需要加上1，表示從原來的子樹中分離出去。由于我們初始化ans的值為dp[root][p],所以我們也無需擔心根節點這個答案+1后超出原來的值。有一些細節需要注意，具體看代碼。 notes: 1. 沒有處理0，而是放在最后處理，因為劃分出來1個節點也是0刀，避免dp沖突，最后再遍歷一遍即可。 2. dp[x][1]就代表其它兄弟節點不貢獻值，所以也不用處理0這種情況。
#include<cstdio>#include<iostream>#include<sstream>#include<cstdlib>#include<cmath>#include<cctype>#include<string>#include<cstring>#include<algorithm>#include<stack>#include<queue>#include<set>#include<map>#include<ctime>#include<vector>#include<fstream>#include<list>#include<numeric>#include<functional>using namespace std;typedef long long ll;typedef unsigned long long ull;#define ms(s) memset(s,0,sizeof(s))const double PI = 3.141592653589;const int INF = 0x3fffffff;int dp[155][155];int fa[155];vector<int> Tree[155];int n, p;void solve(int x) { for(int i = 0; i < Tree[x].size(); i++) solve(Tree[x][i]); dp[x][1] = Tree[x].size(); for(int i = 0; i < Tree[x].size(); i++) { for(int j = p-1; j > 0; j--) { if(dp[x][j] != INF) { for(int k = 1; k <= p-j; k++) { if(dp[Tree[x][i]][k] != INF) dp[x][j+k] = min(dp[x][j+k], dp[Tree[x][i]][k]+dp[x][j]-1); } } } }}int main() {// freopen("/Users/really/Documents/code/input","r",stdin); // freopen("/Users/really/Documents/code/output","w",stdout); ios::sync_with_stdio(false); int a, b, ans, root = 1; ms(fa); for(int i = 0; i <= 150; i++) for(int j = 0; j <= 150; j++) dp[i][j] = INF; cin >> n >> p; for(int i = 1; i < n; i++) { cin >> a >> b; fa[b] = a; Tree[a].push_back(b); } while(fa[root] != 0) root = fa[root]; solve(root); ans = dp[root][p]; for(int i = 1; i <= n; i++) if(dp[i][p] < ans) ans = dp[i][p]+1; cout << ans << endl; return 0;}新聞熱點
疑難解答
