求多叉树根节点的所有子树中节点数量的最大值。

#include <iostream>
#include <unordered_map>
#include <unordered_set>
#include <algorithm>

using namespace std;

unordered_map<int, unordered_set<int>> tree;

int getChildNum(int node, int parent)
{
    int childNum = 0;
    for (int child : tree[node])
    {
        if (child == parent)
        {
            continue;
        }
        childNum++;
        childNum += getChildNum(child, node);
    }
    return childNum;
}

int main()
{
    int n;
    cin >> n;
    for (int i = 0; i < n - 1; i++)
    {
        int x, y;
        cin >> x >> y;
        tree[x].insert(y);
        tree[y].insert(x);
    }
    int maxChildNum = 0;
    for (int child : tree[1])
    {
        int childNum = getChildNum(child, 1) + 1;
        maxChildNum = max(maxChildNum, childNum);
    }
    cout << maxChildNum << endl;
    return 0;
}

动态规划，以串的长度递增的顺序求最大值。

#include <iostream>
#include <string>
#include <vector>

using namespace std;

int main()
{
    int m;
    cin >> m;
    vector<string> strs(m);
    for (int i = 0; i < m; i++)
    {
        cin >> strs[i];
    }
    string t;
    cin >> t;
    int tLength = t.length();
    vector<int> counts(tLength + 1);
    string formed;
    for (int i = 0; i < tLength; i++)
    {
        int count = counts[i];
        formed += t[i];
        for (string &str : strs)
        {
            int strLength = str.length();
            if (strLength > i + 1)
            {
                continue;
            }
            if (str == formed.substr(i - strLength + 1))
            {
                count = max(count, counts[i - strLength + 1] + 1);
            }
        }
        counts[i + 1] = count;
    }

    int result = counts[tLength];
    cout << result << endl;

    return 0;
}