PRoblem: 給一棵樹，問最少砍多少刀就可以劃分出來一個(gè)p個(gè)節(jié)點(diǎn)的子樹。 Solution: 對(duì)于一個(gè)根節(jié)點(diǎn)i，我們定義這個(gè)i一定在最終劃分出來的子樹當(dāng)中，dp[i][k]表示以i為根節(jié)點(diǎn)的子樹劃分出k個(gè)節(jié)點(diǎn)所需要的最少次數(shù)。那么dp[i][j+k] = min(dp[i][j+k], dp[i][j]+dp[son[i]][k]-1)。這個(gè)狀態(tài)轉(zhuǎn)換理解為：對(duì)于i為根節(jié)點(diǎn)的這顆子樹，需要?jiǎng)澐殖鰜韏+k個(gè)節(jié)點(diǎn)，那么我們可以從這個(gè)兒子中劃分出來k個(gè)，從其它部分劃分出來j個(gè)，-1是因?yàn)橐褍鹤幽遣糠趾喜⑦M(jìn)來，就需要減一刀。最終動(dòng)規(guī)完畢后，需要再遍歷一遍所有節(jié)點(diǎn)，找到以哪個(gè)節(jié)點(diǎn)為根節(jié)點(diǎn)的子樹才是最優(yōu)解，而最后需要加上1，表示從原來的子樹中分離出去。由于我們初始化ans的值為dp[root][p],所以我們也無需擔(dān)心根節(jié)點(diǎn)這個(gè)答案+1后超出原來的值。有一些細(xì)節(jié)需要注意，具體看代碼。 notes: 1. 沒有處理0，而是放在最后處理，因?yàn)閯澐殖鰜?個(gè)節(jié)點(diǎn)也是0刀，避免dp沖突，最后再遍歷一遍即可。 2. dp[x][1]就代表其它兄弟節(jié)點(diǎn)不貢獻(xiàn)值，所以也不用處理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;}新聞熱點(diǎn)
疑難解答
圖片精選
網(wǎng)友關(guān)注
