【题目描述】
政府邀请了你在火车站开饭店，但不允许同时在两个相连的火车站开。任意两个火车站有且只有一条路径，每个火车站最多有 50 个和它相连接的火车站。
告诉你每个火车站的利润，问你可以获得的最大利润为多少？
例如下图是火车站网络：
最佳投资方案是 1 ， 2 ， 5 ， 6 这 4 个火车站开饭店可以获得的利润为 90.
【输入格式】
第一行输入整数 N(<=100000), 表示有 N 个火车站，分别用 1,2,……..,N 来编号。接下来 N 行，每行一个整数表示每个站点的利润，接下来 N-1 行描述火车站网络，每行两个整数，表示相连接的两个站点。
【输出格式】
输出一个整数表示可以获得的最大利润。
【样例输入】
6
10
20
25
40
30
30
4 5
4 6
3 4
1 3
2 3
【样例输出】
90
题解： 本题是今天的noip模拟题，第二题，跟之前做的拜访奶牛差不多，是树形DP，呵呵，转移方程是，其实，我不知道哪块算，是一个递归，有点像记忆化搜索！！ C++语言: made by PaulInsider!
#include <iostream>
#include <cstdio> #include <cstdlib>
#define max(a,b) ((a)>=(b)?(a):(b))
using namespace std;
int w[100001],n,m;
int q[100001][2],a[100001][51]; //q表示第i个节点往后的最大利润，因为是树！
int ji[100001]={0},answer;
bool used[100001]={0};
void dp(int x);
int main()
{
freopen ("profitz.in","r",stdin);
freopen ("profitz.out","w",stdout);
scanf("%d",&n);
for (int o=1;o<=n;o++)
{
scanf("%d",&w[o]);
q[o][1]=w[o];
}
for (int o=1;o<=n-1;o++)
{
int c,d;
scanf("%d%d",&c,&d);
ji[c]++;
ji[d]++;
a[c][ji[c]]=d;
a[d][ji[d]]=c;
}
dp(1);
if (q[1][0]<q[1][1])
{
cout<<q[1][1];
}
else
{
cout<<q[1][0];
}
return 0;
}
void dp(int x)
{
used[x]=1;
for (int i=1;i<=ji[x];i++)
{
if (!used[a[x][i]])
{
dp(a[x][i]);
q[x][0]+=max(q[a[x][i]][0],q[a[x][i]][1]);
q[x][1]+=q[a[x][i]][0];
}
}
}
|
