Dynamic programming: digital statistics DP (counting problem)

Digital statistics DP

AcWing 338. Counting problem

Given two integers \ (a \) and \ (b \), find the number of occurrences of \ (0 \sim 9 \) in all numbers between \ (a \) and \ (b \).
For example, \ (a=1024, b=1032 \), the total number of \ (9 \) between \ (a \) and \ (b \) is as follows:
1024 1025 1026 1027 1028 1029 1030 1031 1032
Among them, '0' appears 10 times, '1' appears 10 times, '2' appears 7 times, '3' appears 3 times and so on

Input format
The input contains multiple sets of test data. Each set of test data occupies one line and contains two integers \ (a \) and \ (b \). When a line \ (0 \) is read in, it indicates that the input is terminated and the line is not processed.

Output format
Each group of data outputs a result, and each result occupies one row. Each result contains ten numbers separated by spaces. The first number represents the number of occurrences of '0', the second number represents the number of occurrences of '1', and so on.

Data range
\(0 < a,b < 100000000\)

Input sample:

1 10
44 497
346 542
1199 1748
1496 1403
1004 503
1714 190
1317 854
1976 494
1001 1960
0 0

Output example:

1 2 1 1 1 1 1 1 1 1
85 185 185 185 190 96 96 96 95 93
40 40 40 93 136 82 40 40 40 40
115 666 215 215 214 205 205 154 105 106
16 113 19 20 114 20 20 19 19 16
107 105 100 101 101 197 200 200 200 200
413 1133 503 503 503 502 502 417 402 412
196 512 186 104 87 93 97 97 142 196
398 1375 398 398 405 499 499 495 488 471
294 1256 296 296 296 296 287 286 286 247

Code:

#include <iostream>
#include <algorithm>
using namespace std;

int get(vector<int> num, int l, int r) 
{
    int res = 0;
    for(int i = l; i >= r; i --)
        res = res * 10 + num[i];
    return res;
}

int power10(int x) //Find the x power of 10
{
    int res = 1;  
    while(x --)  res *= 10;
    return res;
}

int count(int n, int x)
{
    if(!n)  return 0;
    
    vector<int> num; //The lower digits are counted first
    while(n)
    {
        num.push_back(n % 10);
        n /= 10;
    }
    
    n = num.size();
    int res = 0;
    for(int i = n - 1 - !x; i >= 0; i --)
    {//Count the number of times x appears in position i from the highest position,! x: When x=0, the highest bit cannot be 0. Enumeration starts from the second bit
        if(i < n - 1)
        {
            res += get(num, n - 1, i + 1) * power10(i);
            if(!x)  res -= power10(i); // When x=0, enumeration starts from 001
        }
        if(num[i] == x)  res += get(num, i - 1, 0) + 1;
        else if(num[i] > x)  res += power10(i);
    }
    return res;
}

int main()
{
    int a, b;
    while(cin >> a >> b, a || b)
    {
        if(a > b)  swap(a, b);
        for(int i = 0; i < 10; i ++)
            cout << count(b, i) - count(a - 1, i) << ' ';
        cout << endl;
    }
    return 0;
}

Tree DP

AcWing 285. A dance without a boss

Ural university has N staff, numbered 1~N. Their relationship is like a tree with the principal as the root, and the parent node is the direct boss of the child node. Each employee has a happiness index, which is given by the integer Hi, where 1 ≤ i ≤ N. Now we are going to hold an anniversary party, but no staff is willing to attend the meeting with their direct supervisor. On the premise of meeting this condition, the organizer hopes to invite some staff to the meeting, so as to maximize the total happiness index of all staff participating in the meeting, and seek this maximum value.

Enter an integer n in the first line of the format. Next, line N and line i represent the happiness index Hi of employee i. Next, in line N-1, enter a pair of integers L and K in each line, indicating that K is the direct supervisor of L.

The output format outputs the maximum happiness index.

Data range 1 ≤ N ≤ 6000, − 128 ≤ Hi ≤ 127 input example: 7 1 1 1 1 1 1 1 3 2 3 6 4 7 4 4 5 3 5 output example: 5

Code: there is a parent-child relationship between the tree root and the root of the subtree. The problems can be roughly divided into: ① if the tree root u is selected, then all subtrees can not choose the root f[u][1] ② if the tree root u is not selected, then all subtrees can choose the root or not choose the root f[u][0] Initial state: f[k][1] = happy[k], f[k][0] = 0 (k is the leaf node) state transition: f[u][1] = ∑ f[si][0], f[u][0] = ∑ max(f[si][0], f[si][1])

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
using namespace std;

const int N = 6010;
int n, h[N], e[N], ne[N], idx;
int happy[N], f[N][2];
bool has_fa[N];

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

void dfs(int u)
{<!-- -->
    f[u][1] = happy[u];
    
    for(int i = h[u]; i != -1; i = ne[i])
    {<!-- -->
        int j = e[i];
        dfs(j);
        f[u][1] += f[j][0];
        f[u][0] += max(f[j][0], f[j][1]);
    }
}
int main()
{<!-- -->
    scanf("%d", &amp;n);
    for(int i = 1; i &lt;= n; i ++) scanf("%d", &amp;happy[i]);
    
    memset(h, -1, sizeof h);
    for(int i = 0; i &lt; n - 1; i ++)
    {<!-- -->
        int a, b;
        scanf("%d%d", &amp;a, &amp;b);
        add(b, a);
        has_fa[a] = true; 
    }
    
    int root = 1;
    while(has_fa[root]) root ++;
    
    dfs(root);
    printf("%d\n", max(f[root][0], f[root][1]));
    return 0;
}