题解 P5054 【[COCI2017-2018#7] Dostavljač】

JK_LOVER · 2020-07-20 21:50:54 · 题解

题意

给你一棵节点个数为 n 的有根树，求出在所给时间内的 ans 最大值。QWQ

分析

对于每一个节点来看

• 停在这个节点了。

• 去遍历子树了。

• 一系列操作之后，返回父亲了。

那么我们可以定义状态。 dp[x][i][0/1] 对于节点 x 考虑，使用了 大小为 i 的时间。其中 0 表示去遍历子树了， 1 表示停在这个节点了。 而返回父亲则可以用 dp[x][i+1][1] 表示，因为再走一步就可以返回父亲。有如下转移方程：

分别表示：

• 儿子返回父亲，父亲停下。

• 父亲停下，去儿子子树。

• 儿子返回，去父亲子树。

时间复杂度为 O(nm^2) 。

代码

#include<bits/stdc++.h>
using namespace std;
int read()
{
    int x=0,f=0;char ch=getchar();
    while(!isdigit(ch)){if(ch=='-')f=1;ch=getchar();}
    while(isdigit(ch)){x=x*10+ch-'0';ch=getchar();}
    return f?-x:x;
}
const int N = 1100;
int dp[N][N][2],n,m,val[N];
vector<int> G[N];
void dfs(int x,int fa)
{
    for(int i = 0;i < G[x].size();i++)
    {
        int y = G[x].at(i);
        if(y == fa) continue;
        dfs(y,x);
        for(int j = m;j >= 0;j--)
        {
            for(int k = m;k >= 0;k--)
            {
                if(k + j + 2 <= m) 
                dp[x][j+k+2][0] = max(dp[x][j+k+2][0],dp[x][j][0]+dp[y][k][1]);
                dp[x][j+k+2][1] = max(dp[x][j+k+2][1],dp[x][j][1]+dp[y][k][1]); 
                if(k + j + 1 <= m)
                dp[x][j+k+1][0] = max(dp[x][j+k+1][0],dp[x][j][1]+dp[y][k][0]);
            }
        }
    }
    for(int i = m;i >= 1;i--)
    dp[x][i][1] = max(dp[x][i][1],dp[x][i-1][1]+val[x]),
    dp[x][i][0] = max(dp[x][i][0],dp[x][i-1][0]+val[x]);
//  for(int i = 1;i <= m;i++)
//  {
//      cout<<"x:: " <<x<<"   i:: "<<i<<"  dp::"<<dp[x][i][0]<<endl;
//  }
}
int main()
{
    n = read();m = read();
    for(int i = 1;i <= n;i++) val[i] = read();
    for(int i = 1;i < n;i++)
    {
        int a = read(),b = read();
        G[a].push_back(b);
        G[b].push_back(a);
    }
    dfs(1,0);
    cout<<dp[1][m][0]<<endl;
    return 0;
}