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
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;
}
投递饿了么等公司10个岗位 >