第十四届蓝桥杯集训——练习解题阶段(无序阶段)-ALGO-987 强力党逗志芃

#include <stdio.h>
#include <stdlib.h>

int n,m;
int score[250]={0};
long long dp[250][250]={0};
int mp[250][250]={0};
long long max(long x,long y);

void f(int cur);

int main()
{
    scanf("%d%d",&n,&m);
    m=m+1;
    int i;
    for(i=1;i<=n;i++)
    {
        scanf("%d",&score[i]);
        mp[0][i]=1;
    }
    for(i=0;i<n-1;i++)
    {
        int c,d;
        scanf("%d%d",&c,&d);
        mp[c][d]=1;
        mp[0][d]=0;
    }
    f(0);
    printf("%lld",dp[0][m]);
    return 0;
}

long long max(long x,long y)
{
    if(x>=y)
        return x;
    else
        return y;
}

void f(int cur)
{
    int i,j,k;
    for(i=1;i<=n;i++)
    {
        if(mp[cur][i]==1)
        {
            f(i);
            for(j=m-1;j>=0;j--)
            {
                for(k=0;k<=j;k++)
                {
                    dp[cur][j]=max(dp[cur][j],dp[cur][j-k]+dp[i][k]);
                }
            }
        }
    }
    for(j=m;j>=0;j--)
    {
        if(j==0)
            dp[cur][0]=0;
        else
            dp[cur][j]=dp[cur][j-1]+score[cur];
    }
}

#include<iostream>
#include<algorithm>
#include<cstring>
using namespace std;

const int N = 210;

int n,m;
int q[N];
int h[N],e[N],ne[N],idx;
int dp[N][N];//以i为根节点，总花费的点数不超过j的最大方案
bool st[N];//是否有前驱
int res = 0;//伤害的最大的值


void add(int x,int y)
{
    e[idx] = y,ne[idx] = h[x],h[x] = idx++;
}

void dfs(int u)
{
    for(int i = h[u];i != -1; i = ne[i])//循环物品组
    {
        int son = e[i];
        dfs(son);

        for(int j = m - 1; j >= 0; j--)//循环剩余的点数
            for(int k = 0; k <= j; k++)//循环决策
                dp[u][j] = max(dp[u][j], dp[u][j - k] + dp[son][k]);
    }

    //将当前的节点1
    for(int i = m; i >= 1; i--) dp[u][i] = dp[u][i - 1] + q[u];
    dp[u][0] = 0;
}

int main()
{
    cin >> n >> m;
    memset(h, -1 ,sizeof h);

    for(int i = 1; i <= n; i++)//读取每个节点的值
        cin>>q[i];

    for(int i = 1; i < n; i++)//读取节点之间的关系
    {
        int x,y;
        cin >> x >> y;
        add(x,y);//x为y的父节点
        st[y] = true;
    }

    int root;//寻找根节点
    for(int i = 1; i <= n; i++)
        if(st[i] == false){
            root = i;
            break;
        }
    
    dfs(root);
	
    cout << dp[root][m] << endl;

    return 0;
}

import java.io.*;
import java.util.ArrayList;
import java.util.List;

public class Main {

    static int[][] dp;
    static TreeNode[] treeNodes = new TreeNode[201];
    static int n;
    static int m;
    static void dfs(int index){
        if (m >= 1) {
            if (treeNodes[index].child.size()   == 0 || 1 == m) {
                for (int i = 1; i <= m; i++){
                    dp[index][i] = treeNodes[index].w;
                }
            }else{
                for (int k = 0; k < treeNodes[index].child.size(); k++){
                    dfs(treeNodes[index].child.get(k));
                    for (int i = m - 1; i > 0; i--){
                        for (int j = 1; j <= i; j++) {
                            dp[index][i] = Math.max(dp[index][i], dp[index][i - j] + dp[treeNodes[index].child.get(k)][j]);
                        }
                    }
                }
                for(int i = m; i >= 1; i--) {
                    dp[index][i] = dp[index][i - 1] + treeNodes[index].w;
                }
            }
        }
    }


    public static void main(String[] args) throws IOException {
        StreamTokenizer in = new StreamTokenizer(new BufferedReader(new InputStreamReader(System.in)));
        PrintWriter out = new PrintWriter(new OutputStreamWriter(System.out));
        in.nextToken();
        n = (int) in.nval;
        in.nextToken();
        m = (int) in.nval;
        dp = new int[201][201];
        for (int i = 1; i <= n; i++){
            treeNodes[i] = new TreeNode();
            in.nextToken();
            treeNodes[i].w = (int) in.nval;
        }
        for(int i = 0; i < n - 1; i++){
            in.nextToken();
            int x = (int) in.nval;
            in.nextToken();
            int y = (int) in.nval;
            treeNodes[x].child.add(y);
        }
        dfs(1);
        out.println(dp[1][m]);
        out.flush();
        out.close();
    }


    static class TreeNode{
        int w;
        List<Integer> child = new ArrayList<>();
    }
}

n,q=map(int,input().split())
we=list(map(int,input().split()))
we.insert(0,0)
gen=[0 for i in range(n)]

dp=[[0 for i in range(n+1)]for j in range(n+1)]
sum=[0 for i in range(n+1)]

def dfs(u,father):
    for i in range(len(edge[u])):
        v=edge[u][i][0]
        w=edge[u][i][1]
        if v==father:
            continue
        dfs(v,u)
        sum[u]+=sum[v]+1
        for j in range(min(q,sum[u]),-1,-1):
            for k in range(min(sum[v],j-1),-1,-1):
                dp[u][j]=max(dp[u][j],dp[u][j-1-k]+dp[v][k]+w)
        


edge=[[]for i in range(n+1)]
for _ in range(n-1):
    a,b=map(int,input().split())
    gen[b-1]=1
    edge[a].append((b,we[b]))
    edge[b].append((a,we[b]))

for i in range(n):
    if gen[i]==0:
        w=we[i+1]
        dfs(i+1,0)
        break
print(dp[1][q-1]+w)