洛谷P4438 [HNOI/AHOI2018]道路(dp)

题意

题目链接

sol

每当出题人想起他出的hnoi 2018 day2t3，他都会激动的拍打着轮椅

读题比做题用时长系列。。。

\(f[i][a][b]\)表示从根到\(i\)的路径上，有\(a\)条公路未被翻修，\(b\)条铁路未被翻修

然后xjb转移一下

比较好奇为啥不会mle..

#include<bits/stdc++.h>
#define ll long long 
using namespace std;
const int maxn = 1e5 + 10;
const ll inf = 1e18;
inline int read() {
    char c = getchar(); int x = 0, f = 1;
    while (c < '0' || c > '9') {if (c == '-')f = -1; c = getchar();}
    while (c >= '0' && c <= '9') {x = x * 10 + c - '0'; c = getchar();}
    return x * f;
}
int n, ls[maxn], rs[maxn];
ll a[maxn], b[maxn], c[maxn];
vector<int> v[maxn];
ll f[20001][41][41];
ll dfs(int x, ll a, ll b) {
    if(x > n) return c[x] * (a[x] + a) * (b[x] + b);
    if(f[x][a][b] <= inf) return f[x][a][b];
    else f[x][a][b] = min(dfs(ls[x], a, b) + dfs(rs[x], a, b + 1), dfs(ls[x], a + 1, b) + dfs(rs[x], a, b));
    return f[x][a][b];
}
int main() {
//  freopen("a.in", "r", stdin);
    memset(f, 0x7f, sizeof(f));
    n = read();
    for(int i = 1; i <= n - 1; i++) {
        ls[i] = read(); rs[i] = read();
        if(ls[i] < 0) ls[i] = -ls[i] + n;
        if(rs[i] < 0) rs[i] = -rs[i] + n;
    }
    for(int i = n + 1; i <= 2 * n; i++) a[i] = read(), b[i] = read(), c[i] = read();
    if(n == 1) cout << 0 << endl;
    else cout << dfs(1, 0, 0);
    return 0;
}