https://vijos.org/p/1180

…

O(nm^2)
https://vijos.org/records/543919bc17f3cade3fb0a871

//}/* .................................................................................................................................. */

const int N = int(3e2) + 9;

VI adj[N]; int f[N][N], val[N];
int n, m;

void dfs(int u = 0){

    ECH(it, adj[u]){
        int v = *it; dfs(v);
        DWN_1(i, m, 1) REP_1(j, i) checkMax(f[u][i], f[u][i-j]+f[v][j]);
    }

    DWN_1(i, m, 1) f[u][i] = f[u][i-1] + val[u];
}

int main(){

#ifndef ONLINE_JUDGE
    //freopen("in.txt", "r", stdin);
    //freopen("out.txt", "w", stdout);
#endif

    REP_1_C(i, RD(n, m)){
        adj[RD()].PB(i);
        RD(val[i]);
    }

    ++m; dfs();
    OT(f[0][m]);
}

O(nm)
https://vijos.org/records/5411eea148c5fcdb208b4568

//}/* .................................................................................................................................. */

const int N = int(3e2) + 9;

VI adj[N]; int f[N][N], val[N];
int n, m;

void dfs(int u = 0){
    ECH(it, adj[u]){
        int v = *it; REP(i, m) f[v][i] = f[u][i] + val[v]; // 强制在 u 的当前状态（所有 dfs 序在 v 之前的节点所形成的泛化物品）中放入物品 v。。作为 v 的初始状态。。。
        dfs(v); REP_1(i, m) checkMax(f[u][i], f[v][i-1]); // 泛化物品的并。。。
    }
}

int main(){

    REP_1_C(i, RD(n, m)){
        adj[RD()].PB(i);
        RD(val[i]);
    }

    dfs();
    OT(f[0][m]);
}

Posted by xiaodao
Category: 日常
Tags: 泛型背包