WorksApplication 无线路由器参考思路

[Exam2] Wireless Routers

Description

Alice just bought a very big house with N rooms and N-1 doors, which each door connects two rooms. Besides, each room have at least one door and at most 3 doors (of course Alice can Go to every room in this house).

However, a modern person cannot live without Wifi, so Alice wants to put M wireless routers in several rooms. As the routers are cheap, only adjacent rooms (which have a door connect to this room) can receive it, and each router works independently.

Since M routers may cannot cover every room, Alice tells you the satisfaction point S[i] she could have if room i have Wifi.

Please help Alice to calculate the maximum satisfaction point she can get in total.

Input

The first line is two integers N (2 <= N <= 1000), M (1 <= M <= N, M <= 100) Then are N lines, each shows the satisfaction S[i] (1 <= S[i] <= 10) point of room i. Then are N-1 lines, each contains two integers x,y, which represents a door is between room x and y.

output

Just output the maximum point of satisfaction.

Limits

Memory limit per test: 256 megabytes

Time limit per test: The faster the better

Compile & Environment

C++

g++ Main.cc -o Main -fno-asm -Wall -lm –static -std=C++0x -DONLINE_JUDGE

Java

J2SE 8

Maximum stack size is 50m

Sample Test

Input

5 1

1 2 3 4 5

2 1

3 2

4 2

5 3

Output

10

参考思路：树形动态规划。

其实这个题涉及的知识点有两个

1、在树上求最优解？直接先设状态为以x为根的子树下的最优解。如果题意里没有指定根，随便定一个根就行了。

注意：考虑子树的时候就不要考虑对父亲的影响了，对父亲的影响在考虑以父亲为根的子树的时候再算。

2、如果这一个状态下的最优解，还受到其他东西的牵制；或者转移的过程中发现需要确定满足条件，那么把这些牵制你的恶心东西，全部加为状态。

换言之，如果你觉得转移不动？加一维状态。

这两个知识点每个都值得开博客讲一下了。

不过我目前急着清理桌面，先这么写一下（这题的题解，代码顺带一贴，保留下来了），之后有空再详细展开。

然后讲思考过程。

首先用知识点1，直接先设状态

f[x]表示以x为根的子树下的，能收获的最大满意度。

转移的时候分3种情况：

1、没有孩子：直接放下去，或者不放

2、有1个孩子A：这个时候受制于孩子的情况了：孩子上放了路由器，我这里放路由器也没加成；孩子A上没放路由器，还得考虑孩子的孩子A放没放路由器，没放，我X这里放下去，可以获得自己X+孩子A的满意度；放了，我X这里放下去，只能额外获得自己X的满意度。

2、有2个孩子：情况类似1个孩子

这个时候发现，情况非常窘迫：我的转移居然受制于前面的情况，这很不动态规划！怎么办？

用知识点2，直接加1维度状态[0/1/2]，表示这个节点的3种覆盖情况：自己的权值就不算在里面；或者自己的权值算在里面，但是自己不放路由器（孩子节点放了）；或者自己身上放一个路由器

然后还有一个问题：最多M个路由器怎么办？我直接取最大不能保证路由器数量不超。继续用知识点2:，再加一维状态，表示这个子树下放了多少个路由器。

所以，最后我们的状态设置为：

f[i][j][0/1/2]表示，

以i为根的子树，这个子树中放了j个路由器，

（0：根没被覆盖，也不放路由器；1：根被覆盖但不放路由器；2：根上放了路由器）的最大价值。

什么？问我转移怎么做？

每个点有最基本的2个选择：放或者不放。

放的话，子树下路由器数量+1，否则不变。

然后暴力枚举这个子树下的路由器数量——1个孩子的话还好，2个孩子的话，请枚举所有左右子树+自己能凑成j个路由器的方案。

对路由器覆盖的3种情况：

0：2个孩子都没路由器（转移源是状态0或1）

1：2个孩子至少有一个放路由器（转移源是状态2+状态0/1/2）

2：管他的孩子什么状态呢！但是请注意，在自己身上放了以后，算价值的时候，考虑孩子的价值有没有算过，算过不要重复算。

（吐槽：一般动态规划真心的，写到状态设置的思路怎么来的就行了……

转移就是根据状态花时间慢慢思考清楚的——怎么来到这个状态一般还是很自然能想清楚的，

而且这题的转移过程，写出数学表达式你更不想看了）

最后讨论时间复杂度：n个点，每个点3m个状态，每个状态转移中，最坏情况是每个点带2个孩子，要枚举所有能凑成m的方法，时间复杂度O(n * m^2)

当然这只是我的脑洞，懒得去实现了。（而且感觉好恶心……）

最后是代码：

#include <stdio.h>
#include <ctype.h>
#include <string.h>
#include <stdlib.h>
#include <limits.h>
#include <math.h>
#include <algorithm>
#include <vector>
using namespace std;
typedef long long ll;

int n,m;
int value[1005];
vector<int> Go[1005];
vector<int> G[1005];

int f[1005][105][3];
//0 not covered
//1 covered but not AP
//2 AP

void dfs(int p,int father){
    G[p].push_back(father);
    for(int i=0;i<Go[p].size();++i){
        if(Go[p][i]!=father){
            G[p].push_back(Go[p][i]);
            dfs(Go[p][i],p);
        }
    }
    if(G[p].size()==1){
        f[p][1][2]=value[p];
        f[p][0][0]=0;
    }else if(G[p].size()==2){
        int pleft=G[p][1];
        f[p][0][0]=0;
        for(int i=1;i<=m;++i){
            f[p][i][0]=max(f[pleft][i][0],f[pleft][i][1]);
            f[p][i][1]=f[pleft][i][2]==0?0:f[pleft][i][2]+value[p];
            f[p][i][2]=max(f[pleft][i-1][0]+value[p]+value[pleft]
                        ,max(f[pleft][i-1][1]+value[p],f[pleft][i-1][2]+value[p]));
        }
    }else{
        int pleft=G[p][1];
        int pright=G[p][2];
        f[p][0][0]=0;
        for(int i=1;i<=m;++i){
            for(int j=0;j<=i;++j){
                f[p][i][0]=max(f[p][i][0],
                            max(f[pleft][j][0],f[pleft][j][1])+max(f[pright][i-j][0],f[pright][i-j][1]));
            }
            for(int j=0;j<=i;++j){
                f[p][i][1]=max(f[p][i][1],
                            max(f[pleft][j][2]==0?0:f[pleft][j][2]+*max_element(f[pright][i-j]+0,f[pright][i-j]+3)+value[p],
                                f[pright][j][2]==0?0:f[pright][j][2]+*max_element(f[pleft][i-j]+0,f[pleft][i-j]+3)+value[p]));
            }
            for(int j=0;j<i;j++){
                for(int a=0;a<=2;a++){
                    for(int b=0;b<=2;b++){
                        int tval=0;
                        if(a==0){
                            tval+=value[pleft];
                        }
                        if(b==0){
                            tval+=value[pright];
                        }
                        f[p][i][2]=max(f[p][i][2],
                                        f[pleft][j][a]+f[pright][i-1-j][b]+value[p]+tval);
                    }
                }
            }
        }
    }
}

int main(){
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++)scanf("%d",&value[i]);
    for(int i=1;i<n;++i){
        int x,y;
        scanf("%d%d",&x,&y);
        Go[x].push_back(y);
        Go[y].push_back(x);
    }
    dfs(1,0);
    int ans=0;
    for(int i=0;i<=m;i++){
        for(int j=0;j<3;++j){
            ans=max(ans,f[1][i][j]);
        }
    }
    printf("%d\n",ans);
    return 0;
}