Chlience

【题解】LOJ 2510 「AHOI / HNOI2018」道路
Problem给定一棵二叉树,每个非叶子节点的两个儿子节点由铁路和公路各一条相连,可选择一条进行修缮每个叶子节点有...
扫描右侧二维码阅读全文
05
2018/12

【题解】LOJ 2510 「AHOI / HNOI2018」道路

Problem

给定一棵二叉树,每个非叶子节点的两个儿子节点由铁路和公路各一条相连,可选择一条进行修缮

每个叶子节点有三个参数 $a_i,b_i,c_i$,设 $x_i$ 为点 $i$ 到根节点需要经过的未修缮公路,$y_i$为未修缮铁路,

请最小化 $\sum c_i(a_i+x_i)(b_i+y_i)$

Solution

因为只有 $40$ 层,所以用 $f[i][j][k]$ 表示在根节点到 $i$ 这个点,有 $j$ 条没有修缮的公路,$k$ 条没有修缮的铁路的最小值

那么设 $son[i][0]$ 为公路连接的城市, $son[i][1]$ 为铁路连接的城市

若 $i$ 为城市

$$ f[i][j][k] = min(f[son[i][0]][j+1][k] + f[son[i][1]][j][k],f[son[i][0]][j][k] + f[son[i][1]][j][k+1]) $$

若 $i$ 为乡村

$$ f[i][j][k] = c_i(a_i+j)(b_i+k); $$

记忆化搜索即可

Though Again

对于每个点来说,我只要确定公路多少条,铁路多少条就行,管你是怎么来的?

仍然考虑从下向上推,我每次能够转移到父亲处确定的位置(少一条公路/铁路或者因为选择修缮这条边所以不变)

既然是 $O(1)$ 的转移岂不是美滋滋?

这样就能愉快的 $A$ 掉这道题了

Code

#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
const LL N = 20010;
LL f[N][42][42];
LL top[N], num;
LL a[N], b[N], c[N];
LL lson[N], rson[N];
LL fa[N * 2], in[N * 2];
LL n;
LL read() {
    LL ans = 0 , flag = 1;
    char ch = getchar();
    while(ch > '9' || ch < '0') {if(ch == '-') flag = - flag; ch = getchar();}
    while(ch >= '0' && ch <= '9') {ans = ans * 10 + ch - '0'; ch = getchar();}
    return ans * flag;
}
LL get(LL x , LL j , LL k) {
    if(x < n) return f[x][j][k];
    else return c[x - n + 1] * (a[x - n + 1] + j) * (b[x - n + 1] + k);
}
int main() {
    n = read();
    for(LL i = 1 ; i < n ; ++ i) {
        lson[i] = read();
        rson[i] = read();
        if(lson[i] < 0) lson[i] = n - lson[i] - 1;
        if(rson[i] < 0) rson[i] = n - rson[i] - 1;
        fa[lson[i]] = fa[rson[i]] = i;
        in[i] += 2;
    }
    queue <LL> q;
    for(LL i = 1 ; i < 2 * n ; ++ i)
        if(in[i] == 0)
            q.push(i);
    while(!q.empty()) {
        LL x = q.front(); q.pop();
        if(x < n) top[++ num] = x;
        if(-- in[fa[x]] == 0)
            q.push(fa[x]);
    }
    for(LL i = 1 ; i <= n ; ++ i) {
        a[i] = read();
        b[i] = read();
        c[i] = read();
    }
    memset(f, 0x3f3f3f3f, sizeof(f));
    for(LL i = 1 ; i < n ; ++ i) {
        LL x = top[i];
        for(LL j = 0 ; j <= 40 ; ++ j)
            for(LL k = 0 ; k <= 40 ; ++ k)
                f[x][j][k] = min(get(lson[x], j, k) + get(rson[x], j, k + 1), get(lson[x], j + 1, k) + get(rson[x], j, k));
    }
    printf("%lld\n" , f[1][0][0]);
    return 0;
}
Last modification:December 5th, 2018 at 05:47 pm
If you think my article is useful to you, please feel free to appreciate

Leave a Comment