SCUT - 216 - 宝华科技树

演员

把这个当成dp算了半天，各种姿势，好吧，就当练习一下树dp。

假如是每个节点的层数之和，按照dp[i][j]为从i点出发获得j科技的最小费用dp是比较好的。

改了改居然也可以过。

#include<bits/stdc++.h>

using namespace std;

typedef long long ll;

vector<pair<int, int> > E[50];

int d[50];

int f[50];

int n, W;

int dp[50][500][3];

//dp[i][j][0]表示i点是叶子的获取总共j点科技需要的最低价格

//dp[i][j][1]表示从i点出发并且i不是叶子的获取总共j点科技需要的最低价格

//dp[i][j][2]表示dp[i][j][1]拷贝

//科技不会超过400

const int INF = 0x3f3f3f3f;

void dfs(int r, int p, int dep, int w) {

    memset(dp[r], INF, sizeof(dp[r]));

    //只走到自己不需要任何价格

    dp[r][dep][0] = 0;

    //不获取任何科技点也不需要任何价格

    dp[r][0][1]=0;

    for(auto e : E[r]) {

        int vi = e.first, wi = e.second;

        dfs(vi, r, dep + 1, wi);

    }

    if(f[r]==-1)

        return;

    int maxk=300;

    for(int k=340;k>=0;--k){

        if(dp[r][k][0]!=INF||dp[r][k][1]!=INF){

            maxk=k;

            //cout<<"maxk="<<maxk<<endl;

            break;

        }

    }

    for(int j = 0; j <= 340; ++j)

        dp[f[r]][j][2]=dp[f[r]][j][1];

    for(int k =maxk; k >= 0; --k) {

        for(int j = k; j <= 340; ++j){

            dp[f[r]][j][2]=min(dp[f[r]][j][2],dp[f[r]][j-k][1]+dp[r][k][0]+w);

            dp[f[r]][j][2]=min(dp[f[r]][j][2],dp[f[r]][j-k][1]+dp[r][k][1]+w);

        }

    }

    for(int j = 0; j <= 340; ++j)

        dp[f[r]][j][1]=dp[f[r]][j][2];

    /*for(int v = 0; v <= 12; ++v) {

        printf("dp[%c][%d][0]=%d\n", r + 'A', v, dp[r][v][0]);

        printf("dp[%c][%d][1]=%d\n", r + 'A', v, dp[r][v][1]);

        printf("dp[%c][%d][0]=%d\n", f[r] + 'A', v, dp[f[r]][v][0]);

        printf("dp[%c][%d][1]=%d\n\n", f[r] + 'A', v, dp[f[r]][v][1]);

    }*/

    return;

}

bool vis[50];

int main() {

#ifdef Yinku

    freopen("Yinku.in", "r", stdin);

#endif // Yinku

    while(~scanf("%d%d", &n, &W)) {

        for(int i = 0; i < 26; ++i) {

            E[i].clear();

            d[i] = 0;

            vis[i] = 0;

        }

        if(n == 1) {

            puts("0");

            continue;

        }

        for(int i = 1; i <= n - 1; ++i) {

            char s[20], t[20];

            int w;

            scanf("%s%s%d", s, t, &w);

            E[s[0] - 'A'].push_back({t[0] - 'A', w});

            d[t[0] - 'A']++;

            f[t[0] - 'A'] = s[0] - 'A';

            vis[s[0] - 'A'] = vis[t[0] - 'A'] = true;

        }

        int r = -1;

        for(int i = 0; i < 26; ++i) {

            if(vis[i] && d[i] == 0)

                r = i;

        }

        f[r]=-1;

        dfs(r, -1, 0, 0);

        int ans = 0;

        for(int i = 340; i >= 0; --i) {

            if(dp[r][i][1] <= W || dp[r][i][0] <= W) {

                ans = max(ans, i);

            }

        }

        printf("%d\n", ans);

    }

    return 0;

}

/*

8 11

A B 8

B C 3

C D 1

D E 1

E F 1

A R 2

R W 9

*/

巴特西

SCUT - 216 - 宝华科技树

最新文章

热门文章