樹狀dp,不簡單。

題意：給出一棵有根樹，問最少切斷幾條邊可以得到有i個結點的子樹（連通分支）。

采用左兒子右兄弟的存儲方式，

dp用兩個數組：

f[i][j]表示以i為根的子樹，形成以本子樹根結點為根（不包含本子樹以外結點），共j個結點的子樹所需的最小消耗。這里并沒有計算切斷i與其父親連接的邊的消耗。

g[i][j]表示以i節點的父親為根的，i結點以及i的父親的子結點鏈中的i以后的結點做根的子樹，構成共j個結點的以i的父親為根（不包含本子樹以外結點）的子樹所需的最小消耗（i的兄弟們在形成子樹時與i的父親相連，即計算消耗時無需切斷與i父親的連接,但j個結點中不包含i的父親）

有狀態轉移方程：g[root][count] = min(g[tree[root].next][count - i] + f[root][i], g[root][count]);

f[root][count +1] = g[tree[root].son][count];

我們只需要把f[i][0]初始化為1，就可以直接把切斷整個以root為根的子樹的情況融合在狀態轉移方程中了。意思就是在以root為根的子樹中取0個點，需要切斷與root的連接，消耗1。

用遞歸的方法來填寫兩個數組。可以形象地認為最外層循環是枚舉count,對于每個count，對樹進行從下到上，對子樹鏈進行從右到左的填寫。

其實用記憶化搜索的方式會更簡便易懂。

View Code #include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
usingnamespace std;

#define maxn 155
#define inf 0x3f3f3f3f

struct Node
{
int son, next, father, num;
} tree[maxn];

int n, p, root;
int f[maxn][maxn], g[maxn][maxn];

void work(int root, int count)
{
if (root ==0)
return;
work(tree[root].son, count);
work(tree[root].next, count);
g[root][count] = inf;
if (tree[root].next)
for (int i =0; i <= count; i++)
g[root][count] = min(g[tree[root].next][count - i] + f[root][i],
g[root][count]);
else
g[root][count] = f[root][count];
f[root][count +1] = inf;
if (count +1> tree[root].num)
return;
f[root][count +1] = g[tree[root].son][count];
}

void cal(int root)
{
if (root ==0)
return;
cal(tree[root].son);
cal(tree[root].next);
int temp = tree[root].son;
tree[root].num =1;
while (temp)
{
tree[root].num += tree[temp].num;
temp = tree[temp].next;
}
}

int main()
{
//freopen("t.txt", "r", stdin);
scanf("%d%d", &n, &p);
memset(tree, 0, sizeof(tree));
for (int i =0; i < n -1; i++)
{
int a, b;
scanf("%d%d", &a, &b);
tree[b].next = tree[a].son;
tree[a].son = b;
tree[b].father = a;
}
for (int i =1; i <= n; i++)
if (tree[i].father ==0)
{
root = i;
break;
}
cal(root);
for (int i =1; i <= n; i++)
f[i][0] =1;
for (int i =0; i < p; i++)
work(root, i);
int ans = inf;
for (int i =1; i <= n; i++)
if (i == root)
ans = min(ans, f[i][p]);
else
ans = min(ans, f[i][p] +1);
printf("%d\n", ans);
return0;
}

總結

以上是生活随笔為你收集整理的poj1947的全部內容，希望文章能夠幫你解決所遇到的問題。

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