首页 > ACM题库 > HDU-杭电 > HDU 3245-Treeland Exhibition-动态规划-[解题报告]HOJ
2014
03-09

HDU 3245-Treeland Exhibition-动态规划-[解题报告]HOJ

Treeland Exhibition

问题描述 :

There are n towns in the treeland � they form a tree, as you may guess, i.e. there is a unique path between every pair of towns. The length of road connecting every pair of adjacent towns is always 1 unit.

You want to hold an exhibition simultaneously on no more than L+1 consecutive towns, i.e. you choose two towns u and v of no more than L unit apart, and set up your exhibition in all the towns on the unique path from u to v. You want to attract people from all over the treeland to your exhibition, so you’d like to minimize the sum of “travelling distance” from every town. The “travelling distance” of a town is the distance from that town to its closest exhibition-town.

输入:

There are at most 25 test cases. Each case begins with two integers, n and L (n <= 10000, 0 < L <= 100), the number of towns, and the maximal distance of the “endpoint towns” you choose. Next n-1 lines contain the descriptions of connections, each with two integers a and b, indicating that town a and town b are directly connected (towns are numbered from 0 to n-1). The input ends with n = L = 0.

输出:

There are at most 25 test cases. Each case begins with two integers, n and L (n <= 10000, 0 < L <= 100), the number of towns, and the maximal distance of the “endpoint towns” you choose. Next n-1 lines contain the descriptions of connections, each with two integers a and b, indicating that town a and town b are directly connected (towns are numbered from 0 to n-1). The input ends with n = L = 0.

样例输入:

3 1
0 1
1 2
4 1
0 1
1 2
2 3
0 0

样例输出:

1
2

好猛的一道题目,做到吐血,最后发现有一组数据栈溢出了,就一组!!!

算了,想法还是最重要的

参考这里,可以和我的文章结合起来看

http://www.cppblog.com/Yuan/archive/2010/09/06/125962.html?opt=admin

首先明确一点,由于是两点之间的一条路径,所以不可能出现下面的情况

 

Treeland Exhibition

即不可能出现三叉路口,出现三叉的就不是两点间的路径了

所以只能是下面两种情况

1、         以u为根时,路径分布在u的两棵子树中,一棵子树中的长度为a,另一棵为

b=L-2-a,(图中红色的路径部分除外)

 

Treeland Exhibition

2、         只延伸出一条路径到一棵子树中

 

Treeland Exhibition

所以在v这棵子树中有L-1长度的路径存在。

我们先假设整棵树以0为根

Dp[u][i]表示以u为根的子树中路径长度为i时的最小代价,u为路径上的一个点,且为端点。 所以以0为根时的状态转移方程为

Dp[u][i]=min(dp[u][i],dp[v][i-1]+sumw[u]-sumw[v]-sum[v]);

sum[u]表示u所在的子树总的点的个数,sumw[u]表示u所在的子树中每个点到u的距离之和,sumw[u]-sumw[v]-sum[v]表示在u的子树中,去掉v所在的子树之后其他子树的点到u的距离之和,因为u为端点,所以其他子树(去除v之后的子树)到路径上的最近点都是u这一点。

所以

dp[v][i-1]+sumw[u]-sumw[v]-sum[v]代表的是分配给v这棵子树i-1长度的路径,u->v相连时的代价,如果这个代价比原先dp[u][i]要小,就更新。

子树有两种选择,取或不取,相当于01背包中每件物品的取或不取。

当然每个节点都有可能为整棵树的根,所以上面的过程只是求出了以0为根时的最少代价ans[0],0在路径上,

所以接下来以每个点(u)为根求这个点为路径上的一点时的最小代价 ,记为ans[u]。

对于每个点为根时的情况,就是我开头画的2、3两张图中情况了

 

第二步中,还是利用sumw[u]-sumw[v]-sum[v](u为根)把v这棵子树去掉,即有一部分路径在v子树中,再加上个dp[v][a]就表示分配给v子树长度为a的路径时最小代价,即sumw[u]+ dp[v][a]-sumw[v]-sum[v],所以dp[v][a]-sumw[v]-sum[v]越小越好,所以可以增加一个tmp[a]数组记录在u的某个子树中最多分配a长度的路径时dp[v][a]-sumw[v]-sum[v]的最小值,并随时更新。

总之,这个题目好猛。

我的代码

#pragma comment(linker,"/STACK:1000000000,1000000000")//猥琐了一下
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
#define min(a,b) a>b?b:a
const int maxn = 10010;
const int INF = 1000000000;
int dp[maxn][110];
int sum[maxn],sumd[maxn];
int head[maxn];
struct Edge{
    int v,next;
}edge[2*maxn];int N,L,E;
void add_edge(int a,int b)
{
    edge[E].v=b;
    edge[E].next=head[a];
    head[a]=E++;
}
void dfs(int u,int fa)
{
    int i,j,k,v;
    sum[u]=1;sumd[u]=0;
    fill(dp[u],dp[u]+L+1,INF);
    for(i=head[u];i!=-1;i=edge[i].next)
    {
        v=edge[i].v;
        if(v==fa) continue;
        dfs(v,u);
        sumd[u]+=sumd[v]+sum[v];
        sum[u]+=sum[v];
    }
    dp[u][0]=sumd[u];
    for(i=head[u];i!=-1;i=edge[i].next)
    {
        v=edge[i].v;
        if(v==fa) continue;
        for(j=1;j<=L;j++)
            dp[u][j]=min(dp[u][j],dp[v][j-1]+sumd[u]-sumd[v]-sum[v]);
    }
}
int ans[maxn];
void solve(int u,int fa)
{
    int i,a,v;
    if(u==0) ans[u]=sumd[0];
    else ans[u]=N-sum[u]+sumd[fa]-sum[u];
    int tmp[110];
    fill(tmp,tmp+L+1,INF); 
    int mi=INF;
    for( i=head[u];i!=-1;i=edge[i].next)
    {
        v=edge[i].v;
        if(v==fa) continue;
        for( a=0;a<=L-2;a++)
            mi=min(mi,tmp[L-2-a]+dp[v][a]-sumd[v]-sum[v]);
        for( a=0;a<=L-1;a++)
        {
            tmp[a]=min(tmp[a],dp[v][a]-sumd[v]-sum[v]);
            if(a) tmp[a]=min(tmp[a],tmp[a-1]);//最多分配a,如果tmp[a-1]更优,就等于tmp[a-1]
        }
    }
    mi=min(mi,tmp[L-1]);
    sumd[u]=ans[u];
    ans[u]+=mi;
    for(i=head[u];i!=-1;i=edge[i].next)
    {
        v=edge[i].v;
        if(v==fa) continue;
        solve(v,u);
    }
}
int main()
{
    int i,j,k,a,b;
    while(scanf("%d%d",&N,&L),(N||L))
    {
        if(N==1) {puts("0");continue;}
        E=0;
        memset(head,-1,sizeof(head));
        for(i=0;i<N-1;i++)
        {
            scanf("%d%d",&a,&b);
            add_edge(a,b);
            add_edge(b,a);
        }
        dfs(0,0);
        solve(0,0);
        printf("%d\n",*min_element(ans,ans+N));
    }
    return 0;
}

 

参考:http://www.cnblogs.com/wuyiqi/archive/2012/03/07/2384202.html


  1. 第一题是不是可以这样想,生了n孩子的家庭等价于n个家庭各生了一个1个孩子,这样最后男女的比例还是1:1