读取编码 UTF-85.13KB

动态规划：数位统计DP(计数问题)、树形DP(没有上司的舞会)

数位统计DP

AcWing 338. 计数问题

给定两个整数 a 和 b，求 a 和 b 之间的所有数字中0~9的出现次数。 例如，a=1024，b=1032，则 a 和 b 之间共有9个数如下： 1024 1025 1026 1027 1028 1029 1030 1031 1032 其中‘0’出现10次，‘1’出现10次，‘2’出现7次，‘3’出现3次等等…

输入格式 输入包含多组测试数据。 每组测试数据占一行，包含两个整数 a 和 b。 当读入一行为0 0时，表示输入终止，且该行不作处理。

输出格式 每组数据输出一个结果，每个结果占一行。 每个结果包含十个用空格隔开的数字，第一个数字表示‘0’出现的次数，第二个数字表示‘1’出现的次数，以此类推。

数据范围 0输入样例： 1 10 44 497 346 542 1199 1748 1496 1403 1004 503 1714 190 1317 854 1976 494 1001 1960 0 0 输出样例： 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) //求出10的x次方
{
    int res = 1;  
    while(x --)  res *= 10;
    return res;
}

int count(int n, int x)
{
    if(!n)  return 0;
    
    vector<int> num; //先计入的是数位低的数字
    while(n)
    {
        num.push_back(n % 10);
        n /= 10;
    }
    
    n = num.size();
    int res = 0;
    for(int i = n - 1 - !x; i >= 0; i --)
    {//从最高位统计x在第i位出现的次数，!x:当x=0时最高位不能为0，从第二位开始枚举
        if(i < n - 1)
        {
            res += get(num, n - 1, i + 1) * power10(i);
            if(!x)  res -= power10(i); // 当x=0时，从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;
}

树形DP

AcWing 285.没有上司的舞会

Ural大学有N名职员，编号为1~N。 他们的关系就像一棵以校长为根的树，父节点就是子节点的直接上司。 每个职员有一个快乐指数，用整数 Hi 给出，其中 1≤i≤N。 现在要召开一场周年庆宴会，不过，没有职员愿意和直接上司一起参会。 在满足这个条件的前提下，主办方希望邀请一部分职员参会，使得所有参会职员的快乐指数总和最大，求这个最大值。

输入格式 第一行一个整数N。 接下来N行，第 i 行表示 i 号职员的快乐指数Hi。 接下来N-1行，每行输入一对整数L, K,表示K是L的直接上司。

输出格式 输出最大的快乐指数。

数据范围 1≤N≤6000, ?128≤Hi≤127 输入样例： 7 1 1 1 1 1 1 1 1 3 2 3 6 4 7 4 4 5 3 5 输出样例： 5

Code: 树根和子树的根存在上下级的关系，问题可大致分为： ①选择树根u，则所有子树不可选根 f[u][1] ②不选择树根u，则所有子树可选根，也可不选根 f[u][0]. 初始状态：f[k][1] = happy[k], f[k][0] = 0（k为叶子结点） 状态转移：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", &n);
    for(int i = 1; i <= n; i ++) scanf("%d", &happy[i]);
    
    memset(h, -1, sizeof h);
    for(int i = 0; i < n - 1; i ++)
    {
        int a, b;
        scanf("%d%d", &a, &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;
}