855学习记录算法动态规划$Day$-$3$——炎泽汐$de$ Blog

计数类$DP$：整数划分

---

//计数 DP：整数划分（完全背包问题思路） 
int IntegerPartitioning(int n, int M){
    int DP[n + 1];
    DP[0] = 1; 
	
    for(int i = 1; i <= n; i++){
        for(int j = i; j <= n; j++){
            //前 i-1 个数组成 j 的方法加上前 i 个数组成 j-i 的方法 
            DP[j] = (DP[j] + DP[j - i]) % M;
        }
    }
	
    return DP[n];
}

//计数 DP：整数划分 
int IntegerPartitioning(int n, int M){
    int DP[n + 1][n + 1];
    DP[0][0] = 1; 
	
    for(int i = 1; i <= n; i++){
        for(int j = 1; j <= i; j++){
            //j 个数可以表达成和为 i 的方案数
            //转移方程是最小值不为 1 的方案加上最小值为 1 的方案 
            DP[i][j] = (DP[i - 1][j - 1] + DP[i - j][j]) % M;
        }
    }

    int res = 0;
    for(int i = 1; i <= n; i++){
        res = (res + DP[n][i]) % M; 
    }
	
    return res;
}

数位统计$DP$：计数问题

---

int get(int n){
    int res = 0;
    while(n){
    	res++;
    	n /= 10;
	}
    return res;
}

//求出数 x 在 0~n 中出现的次数
int count(int n, int x){
    int res = 0, dgt = get(n);
    
    // 循环每一位，累加数 x 在每一位上出现的次数
    for(int i = 1; i <= dgt; i++ ) {
        int p = pow(10, dgt - i);
        // l 代表当前枚举到的位左边的数
        int l = n / p / 10;
        // r 代表当前枚举到的位右边的数
        int r = n % p;
        // dj 代表当前枚举到的位上的数
        int dj = n / p % 10;
        
        if(x != 0){
            res += l * p;
        }else{
            res += (l - 1) * p;
        }
        if(x == dj){
            res += r + 1;
        }
        if(x < dj){
            res += p;
        }
    }
    return res;
}

void CountingProblem(int a, int b){
    if(a > b){
        swap(a, b);
    }
    for(int i = 0; i <= 9; i++ ){
        cout << count(b, i) - count(a - 1, i) << ' ';
    }
}

树形$DP$：没有上司的舞会

---

//树形 DP：没有上司的舞会
#include<bits/stdc++.h>
#define ll long long
#define endl "\n"
#define mem(vis, num) memset(vis, num, sizeof(vis))

using namespace std;

const int N = 6010;

int n;
int happy[N];
int h[N], e[N], ne[N], idx;
int DP[N][2];
bool has_father[N];

void add(int a, int b){
    e[idx] = b, ne[idx] = h[a], h[a] = idx++;
}

void dfs(int u){
    DP[u][1] = happy[u];
    
    for(int i = h[u]; i != -1; i = ne[i]){
        int j = e[i];
        dfs(j);
        
        DP[u][0] += max(DP[j][0], DP[j][1]);
        DP[u][1] += DP[j][0];
    }
}

//f[u,0]表示所有从以 u 为根的子树中选择，并且不选择 u 这个点的方案
//f[u,1]表示所有从以 u 为根的子树中选择，并且选择 u 这个点的方案

int main(){
    cin >> n;
    for(int i = 1; i <= n; i++ ){
    	cin >> happy[i];
	}
    
    mem(h, -1);
    for (int i = 0; i < n - 1; i ++ ) {
        int a, b;
        cin >> a >> b;
        has_father[a] = true;
        add(b, a);
    }
    
    int root = 1;
    while(has_father[root]){
    	root++;
	}
    
    dfs(root);
    
    cout << max(DP[root][0], DP[root][1]) << endl;
    
    return 0;
}