某日企笔试第二题

74 阅读 0 评论 49 点赞

我是靠谱客的博主强健星星，最近开发中收集的这篇文章主要介绍某日企笔试第二题，觉得挺不错的，现在分享给大家，希望可以做个参考。

概述


1 #include <bits/stdc++.h>

2

3 using namespace std;

4 const int N=1005,M=105;

5 int n,m;

6 vector <int> G[N];

7 bool vis[N];

8 int val[N];

9 int dp[N][M][4];
 10 void init()
 11 {
 12
for(int i=1; i<=n; i++) G[i].clear();
 13
memset(vis,0,sizeof(vis));
 14
memset(dp,0,sizeof(dp));
 15 }
 16 void input()
 17 {
 18
for(int i=1; i<=n; i++)
scanf("%d",&val[i]);
 19
for(int i=0; i<n-1; i++)
 20 
{
 21
int x,y;
 22
scanf("%d %d",&x,&y);
 23 
G[x].push_back(y);
 24 
G[y].push_back(x);
 25 
}
 26 }
 27 void dfs1(int i,vector <int> &son,int d[],int sum[],int fa)
 28 {
 29
int sz=son.size();
 30
if(i==sz)
 31 
{
 32
int D=100,SUM=0;
 33
for(int i=0; i<sz; i++)
 34 
{
 35
if(sum[i]) D=min(D,d[i]+1);
 36
SUM+=sum[i];
 37
if(SUM>m) return;
 38 
}
 39
if(D>2) D=2;
 40
int VAL=0;
 41
for(int i=0; i<sz; i++)
 42 
{
 43
VAL+=dp[son[i]][sum[i]][d[i]];
 44 
}
 45
if(D==1) VAL+=val[fa];
 46
dp[fa][SUM][D]=max(dp[fa][SUM][D],VAL);
 47
if(SUM+1>m) return;
 48
VAL=val[fa];
 49
for(int i=0; i<sz; i++)
 50 
{
 51
if(d[i]==2) VAL+=val[son[i]];
 52
VAL+=dp[son[i]][sum[i]][d[i]];
 53 
}
 54
dp[fa][SUM+1][0]=max(dp[fa][SUM+1][0],VAL);
 55
return;
 56 
}
 57
for(sum[i]=0; sum[i]<=m; sum[i]++) for(d[i]=0; d[i]<=2; d[i]++) dfs1(i+1,son,d,sum,fa);
 58 }
 59 void dfs(int u)
 60 {
 61
vis[u]=1;
 62
int t[105];
 63
vector <int> temp;
 64
for(int i=0; i<G[u].size(); i++)
 65 
{
 66
int v=G[u][i];
 67
if(vis[v]) continue;
 68 
temp.push_back(v);
 69 
dfs(v);
 70 
}
 71
int d[3],sum[3];
 72
dfs1(0,temp,d,sum,u);
 73 }
 74 int main()
 75 {
 76
while(cin>>n>>m)
 77 
{
 78 
init();
 79 
input();
 80
for(int i=1; i<=n; i++) if(G[i].size()==1)
 81 
{
 82 
dfs(i);
 83
for(int u=1; u<=n; u++)
 84 
{
 85
int MAX=0;
 86
for(int d=0; d<3; d++) for(int j=0; j<=m; j++)
 87 
{
 88
if(u==4||u==1) printf("dp[%d][%d][%d]=%dn",u,j,d,dp[u][j][d]);
 89
MAX=max(MAX,dp[u][j][d]);
 90 
}
 91
printf("%d: %dn",u ,MAX);
 92 
}
 93
int MAX=0;
 94
for(int d=0; d<3; d++) for(int j=0; j<=m; j++) MAX=max(MAX,dp[i][j][d]);
 95
printf("%dn",MAX);
 96
break;
 97 
}
 98 
}
 99
return 0;
100 }