树状DP（记忆化搜索）PAT甲级 1079 1090 1106

树状dp：用来求树中任意节点到根节点的距离

模板：

int dfs(int i){
    if(f[i] != -1) return f[i];
    if(p[i] == -1) return f[i] = 0;
    return f[i] = dfs(p[i]) + 1;
}

原题链接：

1079 供应链总销售额

1090 供应链最高价格

1106 供应链最低价格

题目：

供应链总销售额

供应链是由零售商，经销商和供应商构成的销售网络，每个人都参与将产品从供应商转移到客户的过程。

整个销售网络可以看作一个树形结构，从根部的供应商往下，每个人从上一级供应商中买入商品后，假定买入价格为 P，则会以高出买入价 r% 的价格向下出售。

只有零售商（即叶节点）可以直接将产品销售给顾客。

现在，给定整个销售网络，请你计算所有零售商的总销售额。

输入格式
第一行包含三个数，N 表示供应链总成员数（所有成员编号从 0 到 N−1，根部供应商编号为 0），P 表示根部供应商的每件产品的售卖价格，r，溢价百分比。

接下来 N 行，每行包含一个成员的信息，格式如下：

Ki ID[1] ID[2] … ID[Ki]
其中第 i 行，Ki 表示从供应商 i 直接进货的成员数，接下来 Ki 个整数是每个进货成员的编号。

如果某一行的 Kj 为 0，则表示这是零售商，那么后面只会跟一个数字，表示卖给客户的产品总件数。

输出格式
输出总销售额，保留一位小数。

数据范围
1≤N≤105,
0<P≤1000,
0<r≤50
每个零售商手中的产品不超过 100 件。
最终答案保证不超过 1010。

输入样例：
10 1.80 1.00
3 2 3 5
1 9
1 4
1 7
0 7
2 6 1
1 8
0 9
0 4
0 3
输出样例：
42.4

我的解法：

#include <bits/stdc++.h>
using namespace std;

const int N = 100010;
double R, P;
int p[N], f[N], cnt[N];

int dfs(int i){
    if(f[i] != -1) return f[i];
    if(p[i] == -1) return f[i] = 0;
    return f[i] = dfs(p[i]) + 1;
}
int main(){
    int n;
    cin >> n >> P >> R;
    memset(f, -1, sizeof f);
    memset(p, -1, sizeof p);
    for(int i = 0; i < n; i ++ ){
        int k;
        cin >> k;
        for(int j = 0; j < k; j ++ ){
            int son;
            cin >> son;
            p[son] = i;
        }
        
        if(k == 0) cin >> cnt[i];
    }
    
    double res = 0;
    for(int i = 0; i < n; i ++ ){
        if(cnt[i]){
            res += cnt[i] * P * pow(1 + R/100, dfs(i));
        }
    }
    
    printf("%.1lf", res);
    return 0;
}

供应链最高价格

供应链是由零售商，经销商和供应商构成的销售网络，每个人都参与将产品从供应商转移到客户的过程。

整个销售网络可以看作一个树形结构，从根部的供应商往下，每个人从上一级供应商中买入商品后，假定买入价格为 P，则会以高出买入价 r% 的价格向下出售。

只有零售商（即叶节点）可以直接将产品销售给顾客。

现在，给定整个销售网络，请你计算零售商能达到的最高销售价格。

输入格式
第一行包含三个数，N 表示供应链总成员数（所有成员编号为 0 到 N−1)；P 表示根部供应商的产品销售价格；r，表示溢价百分比。

第二行包含 N 个数字，第 i 个数字 Si 是编号为 i 的成员的上级供应商的编号。根部供应商的 Sroot 为 -1。

输出格式
输出零售商可达到的最高销售价格，保留两位小数，以及可达到最高销售价格的零售商的数量。

数据范围
1≤N≤105,
0<P≤1000,
0<r≤50,
最终答案保证不超过 1010。

输入样例：
9 1.80 1.00
1 5 4 4 -1 4 5 3 6
输出样例：
1.85 2

我的解法：

#include <bits/stdc++.h>
using namespace std;

const int N = 100010;
int n;
double P, R;
int p[N], f[N];

int dfs(int i){
    if(f[i] != -1) return f[i];
    if(p[i] == -1) return f[i] = 0;
    return f[i] = dfs(p[i]) + 1;
}

int main(){
    cin >> n >> P >> R;
    
    memset(p, -1, sizeof p);
    for(int i = 0; i < n; i ++ ){
        int father;
        cin >> father;
        p[i] = father;
    }
    
    memset(f, -1, sizeof f);
    
    int cnt = 0, res = 0;
    for(int i = 0; i < n; i ++ ){
        if(dfs(i) > res){
            res = dfs(i);
            cnt = 1;
        }
        else if(dfs(i) == res) cnt ++;
    }
    
    printf("%.2lf %d", P * pow(1 + R / 100, res), cnt);
    return 0;
}

供应链最低价格

供应链是由零售商，经销商和供应商构成的销售网络，每个人都参与将产品从供应商转移到客户的过程。

整个销售网络可以看作一个树形结构，从根部的供应商往下，每个人从上一级供应商中买入商品后，假定买入价格为 P，则会以高出买入价 r% 的价格向下出售。

只有零售商（即叶节点）可以直接将产品销售给顾客。

现在，给定整个销售网络，请你计算零售商能达到的最低销售价格。

输入格式
第一行包含三个数，N 表示供应链总成员数（所有成员编号从 0 到 N−1，根部供应商编号为 0），P 表示根部供应商的产品售卖价格，r，溢价百分比。

接下来 N 行，每行包含一个成员的信息，格式如下：

Ki ID[1] ID[2] … ID[Ki]
其中第 i 行，Ki 表示从供应商 i 直接进货的成员数，接下来 Ki 个整数是每个进货成员的编号。

如果 Kj 为 0 则表示第 j 名成员是零售商。

输出格式
输出零售商可达到的最低销售价格，保留四位小数，以及可达到最低销售价格的零售商的数量。

数据范围
1≤N≤105,
0<P≤1000,
0<r≤50,
最终答案保证不超过 1010
输入样例：
10 1.80 1.00
3 2 3 5
1 9
1 4
1 7
0
2 6 1
1 8
0
0
0
输出样例：
1.8362 2

我的解法：

#include <bits/stdc++.h>
using namespace std;
const int N = 100010, INF = 1e9;
int n;
double P, R;
int p[N], f[N];
bool is_leaf[N];

int dfs(int i){
    if(f[i] != -1) return f[i];
    if(p[i] == -1) return f[i] = 0;
    return f[i] = dfs(p[i]) + 1;
}

int main(){
    cin.tie();
    cin >> n >> P >> R;
    memset(p, -1, sizeof p);

    for(int i = 0; i < n; i ++ ){
        int k;
        cin >> k;
        for(int j = 0; j < k; j ++ ){
            int son;
            cin >> son;
            p[son] = i;
        }
        if(k == 0) is_leaf[i] = true;
    }
    

    memset(f, -1, sizeof f);
    int res = INF, cnt = 0;
    for(int i = 0; i < n; i ++ ){
        if(is_leaf[i]){
            if(dfs(i) < res){
                res = dfs(i);
                cnt = 1;
            }
            else if(dfs(i) == res) cnt ++ ;
        }
    }
    
    printf("%.4lf %d", P * pow(1 + R / 100, res), cnt);
    return 0;
}