poj 1947 树型DP（依赖背包）

题目：http://poj.org/problem?id=1947

题意：给一颗树包含N个节点，问你最少剪去几个边可以得到一颗包含P个节点的子树。

解题思路：这个题目让我想了一天加一晚上，开始一直想用DP[i][j]表示以i为父节点的树，保留j个子节点至少要剪的边数，结果一直想不出思路，实在没办法，在网上找的解题报告很多也是这个想法，但是在我的不解努力中，终于找到一个独树一帜的解题思路：用DP[i][j]表示，以i为父节点的树，删去j个点，至少要剪去几条边。这样就和原来的思路 相反了，然后解题就一下子简单了好多，直接就是一个很简单很简单的树型dp了，也就是一个很裸的依赖背包了。然后自己写了一个，感觉比参考的代码还要高效！！

解题感想：遇到问题时，如果用一种常规的思路一直解决不了，那么也许用一个相反的思路就可以把问题变的很简单，很简单了。

代码如下：

//1947	Accepted	392K	0MS	C++	1271B	2012-07-24 08:04:30
#include <stdio.h>
#include <cstring>
#include <iostream>
#include <vector>
using namespace std;
#define N 200
#define M (1<<30)
vector <int> tree[N];
int num,remain,root,ans;
int dp[N][N];//dp[i][j]表示以i为根，删除j个还在最少需要删几个边
int dfs(int key)
{
    int length=tree[key].size(),size=1;
    int i,j,k,v,p;
    for(i=0;i<length;i++)
    {
        v=tree[key][i];
        p=dfs(v);   size+=p;
        for(j=num-remain;j>0;j--)
            for(k=1;k<=min(j,p);k++)
                dp[key][j]=min(dp[key][j],dp[key][j-k]+dp[v][k]);
    }
    dp[key][size]=1;
    if(key!=root&&size>=remain)
        ans=min(ans,dp[key][size-remain]+1);
    tree[key].clear();
    return size;
}
void init()
{
    int i,x,y;    bool de[N];
    ans=M;
    memset(de,true,sizeof(de));
    for(i=1;i<num;i++)
    {
        scanf("%d%d",&x,&y);
        tree[x].push_back(y);
        de[y]=false;
    }
    for(i=1;i<num;i++)
        if(de[i])
        {
            root=i;break;
        }
    for(i=1;i<=num;i++)
    {
        dp[i][0]=0;
        for(int j=1;j<=num;j++)
        dp[i][j]=M;
    }
}
int main()
{
    while(cin>>num>>remain)
    {
        init();
        ans=min(ans,dp[root][dfs(root)-remain]);
        cout<<ans<<endl;
    }
}

 
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
const int N = 510;
const int MAX = (1 << 30);
using namespace std;

struct Edg{
    int nod,next;
}edg[2 * N];
int nod[N],k;
bool vis[N];
int dp[N][N];
int ans,n,remain;

void add_edg(int x,int y){
    edg[k].nod = y;
    edg[k].next = nod[x];
    nod[x] = k ++;
}

void init(){
    int x,y;
    k = 0;  ans = MAX;
    memset(vis,sizeof(vis));
    memset(nod,-1,sizeof(nod));
    cin >> n >> remain;
    for(int i = 0; i < n - 1; i ++){
        cin >> x >> y;
        add_edg(x,y);
        add_edg(y,x);
    }
    for(int i = 1;i <= n ;i ++){
        dp[i][0] = 0;
        for(int j = 1; j <= n; j ++)
            dp[i][j] = MAX;
    }
}

int dfs(int key){
    vis[key] = false;
    int v,p,size = 1;
    for(int i = nod[key]; i != -1; i = edg[i].next){
        v = edg[i].nod;
        if(!vis[v]) continue;
        p = dfs(v); size += p;
        for(int j = n - remain; j > 0; j --){
            for(int k = 1; k <= min(p,j);k ++){
                dp[key][j] = min(dp[key][j],dp[key][j - k] + dp[v][k]);
            }
        }
    }
    if(key == 1) dp[key][size] = 0;
    else dp[key][size] = 1;
    if(key != 1 && size >= remain)
        ans = min(ans,dp[key][size - remain] + 1);
    return size;
}

int main(){
    //freopen("1.txt","r",stdin);
    //freopen("2.txt","w",stdout);
    int T,cas = 1;
    cin >> T;
    while(T --){
        init();
        ans = min(ans,dp[1][dfs(1) - remain]);
        printf("case #%d: %dn",cas ++,ans);
    }
}        

（编辑：李大同）

【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容!