算法思想

• 每个下标i都会对应一个它所在组的长度（groupSize[i]），将所有长度相同的下标i放在一起，假设总共k个数，假设当前组容量为c，那么可以划分出的组数为k / c。因为题目保证有解，所以肯定是可以除尽的。
• 然后按照c个容量为一组划分k个数，可以划分出k / c组。

代码

class Solution {
private:
    unordered_map<int, vector<int>> ht;
public:
    vector<vector<int>> groupThePeople(vector<int>& groupSizes) {
        int n = groupSizes.size();
        for(int i = 0; i < n; i ++)
        {
            int k = groupSizes[i];
            ht[k].push_back(i);
        }


        vector<vector<int>> res;

        for(auto [k, vec] : ht)
        {
            vector<int> t;
            for(int i = 0; i < vec.size(); i ++)
            {
                t.push_back(vec[i]);
                if((i + 1) % k == 0)
                {
                    res.push_back(t);
                    t.clear();
                }
            }
        }


        return res;
    }
};

class Solution {
private:
    unordered_map<int, vector<int>> ht;
public:
    vector<vector<int>> groupThePeople(vector<int>& groupSizes) {
        int n = groupSizes.size();
        for(int i = 0; i < n; i ++)
        {
            int k = groupSizes[i];
            ht[k].push_back(i);
        }


        vector<vector<int>> res;

        for(auto [k, vec] : ht)
        {
            vector<int> t;
            for(int i = 0; i < vec.size(); i ++)
            {
                t.push_back(vec[i]);
                if((i + 1) % k == 0)
                {
                    res.push_back(t);
                    t.clear();
                }
            }
        }


        return res;
    }
};

树形dp

#include<iostream>
#include<algorithm>
#include<cstring>
using namespace std;
const int N = 2E5 + 10, M = N * 2;
int h[N], e[M], ne[M], idx;
int d1[N], d2[N], p[N], up[N];
int n, ans;
void insert(int a, int b){
    e[idx] = b, ne[idx] = h[a], h[a] = idx ++;
}
int dfs_down(int u, int father){
// 计算出子结点向下的最长路径和次长路径
// 然后用子结点的信息更新父结点的信息
    for(int i = h[u]; i != -1; i = ne[i]){
        int j = e[i];
        if(j == father) continue;
        int d = dfs_down(j, u) + 1;
        if(d >= d1[u]){
            d2[u] = d1[u];
            d1[u] = d;
            p[u] = j;
        }else if(d > d2[u]) d2[u] = d;
    }

    return d1[u];
}
void dfs_up(int u, int father){ 
// 使用父结点的信息更新子结点的信息
// 然后子结点向上路径
    for(int i = h[u]; i != -1; i = ne[i]){
        int j = e[i];
        if(j == father) continue;
        if(p[u] == j) up[j] = max(up[u], d2[u]) + 1;
        else up[j] = max(up[u], d1[u]) + 1;

        dfs_up(j, u);
    }
}
int main(){
    scanf("%d", &n);
    memset(h, -1, sizeof h);
    for(int i = 1; i < n; i ++){
        int a, b;
        scanf("%d %d", &a, &b);
        insert(a, b), insert(b, a);
    }
    dfs_down(0, -1);
    dfs_up(0 ,-1);

    for(int i = 0; i < n; i ++)
        ans = max(ans, d1[i] + up[i]);

/*
点取得最长路径的三种情况：
①：向下最长路径 + 向上路径
②：向下最长路径 + 向下次长路径
③：向下次长路径 + 向上路径
但是很明显①的情况优于③，所以只需要枚举情况①、②
*/ 
    for(int i = 0; i < n; i ++)
        if(ans == d1[i] + up[i] || ans == d1[i] + d2[i])
            printf("%d\n", i);
    return 0; 
}

区间dp

#include<iostream>
#include<algorithm>
#include<cstring>
using namespace std;
const int N = 110;
char s[N];
int f[N][N];
bool is_equal(char a, char b)
{
    if(a == '(' && b == ')') return true;
    if(a == '[' && b == ']') return true;
    return false;
}
int main()
{
    cin >> s + 1;
    int n = strlen(s + 1);

    for(int len = 2; len <= n; len ++)
        for(int i = 1; i + len - 1 <= n; i ++)
        {
            int j = i + len - 1;
            if(is_equal(s[i], s[j])) f[i][j] = f[i + 1][j - 1] + 2;

            for(int k = i; k < j; k ++)
                f[i][j] = max(f[i][j], f[i][k] + f[k + 1][j]);
        }

    cout << n - f[1][n] << endl;
    return 0;
}

线性dp

#include<iostream>
using namespace std;
const int N = 15;
int f[N][N];
int n, m;
int main()
{
    int T;
    cin >> T;
    while(T --)
    {
        cin >> n >> m;

        for(int i = 0; i <= m; i ++)
            f[0][i] = 1;

        for(int i = 1; i <= n; i ++)
            for(int j = 1; j <= m; j ++)
            {
                f[i][j] = f[i][j - 1];
                if(i >= j) f[i][j] += f[i - j][j];
            }

        cout << f[n][m] << endl;
    }
    return 0;
}

记忆化搜索

#include<iostream>
#include<cstring>
using namespace std;
const int N = 15;
int n, m;
int f[N][N];
int dp(int x, int y)
{
    if(x == 0) return 1;
    if(y == 0) return 0;

    if(f[x][y] != -1) return f[x][y];
    int v = 0;
    if(x >= y) v += dp(x - y, y);

    v += dp(x, y - 1);

    return f[x][y] = v;
}
int main()
{
    int T;
    cin >> T;
    while(T --)
    {
        memset(f, -1, sizeof f);
        cin >> n >> m;
        cout << dp(n, m) << endl;
    }
    return 0;
}

完全背包问题 + 数论

#include<iostream>
#include<algorithm>
using namespace std;
const int N = 110, M = 10010;
int f[M];
int a[N];
int gcd(int a, int b)
{
    if(b == 0) return a;
    return gcd(b, a % b);
}
int main()
{
    int n;
    cin >> n;

    int d;
    cin >> a[1]; 
    d = a[1];

    for(int i = 2; i <= n; i ++)
    {

        cin >> a[i];
        d = gcd(a[i], d);
    }


    if(d != 1) cout << "INF"  << endl;
    else
    {
        f[0] = true;

        for(int i = 1; i <= n; i ++)
            for(int j = a[i]; j <= M; j ++)
                f[j] = f[j] | f[j - a[i]];

        int ans = 0;

        for(int i = 1; i <= 10000; i ++)
            if(!f[i]) ans ++;

        cout << ans << endl;
    }

    return 0;
}

线性dp

#include<iostream>
#include<algorithm>
using namespace std;
const int N = 45, M = 355;
int f[N][N][N][N];
int n, m;
int y1, y2, y3, y4;
int a[M];
int main()
{
    cin >> n >> m;

    for(int i = 0; i < n; i ++)
        cin >> a[i];

    for(int i = 1; i <= m; i ++)
    {
        int x;
        cin >> x;
        if(x == 1) y1 ++;
        else if(x == 2) y2 ++;
        else if(x == 3) y3 ++;
        else y4 ++;
    }

    for(int A = 0; A <= y1; A ++)
        for(int B = 0; B <= y2; B ++)
            for(int C = 0; C <= y3; C ++)
                for(int D = 0; D <= y4; D ++)
                {
                    int t = a[A + 2 * B + 3 * C + 4 * D];
                    int& v = f[A][B][C][D];
                    v = t;
                    if(A) v = max(v, f[A - 1][B][C][D] + t);
                    if(B) v = max(v, f[A][B - 1][C][D] + t);
                    if(C) v = max(v, f[A][B][C - 1][D] + t);
                    if(D) v = max(v, f[A][B][C][D - 1] + t);
                }

    cout << f[y1][y2][y3][y4] << endl;
    return 0;
}

数学

#include<iostream>
#include<algorithm>
using namespace std;
const int N = 110;
int w[N];
int main()
{
    int T;
    cin >> T;
    while(T --)
    {
        int n;
        cin >> n;

        for(int i = 0; i < n; i ++)
            cin >> w[i];

        sort(w, w + n, greater<int>());

        for(int i = 0; i < n; i ++)
            cout << w[i] << ' ';

        cout << endl;
    }
    return 0;
}

贪心

#include<iostream>
#include<algorithm>
using namespace std;
int n, x, y, p, k;
int main(){
    cin >> n >> k >> p >> x >> y;

    int sum = 0, lt = 0, ge = 0;
    for(int i = 1; i <= k; i ++)
    {
        int t;
        cin >> t;
        if(t < y) lt ++;
        else ge ++;
        sum += t;
    }
    int r = max(n / 2 + 1, ge), l = n - r;
    if(lt > l) puts("-1");
    else{
        sum += (l - lt) * 1 + (r - ge) * y;

        if(sum > x) puts("-1");
        else {

            for(int i = 1; i <= (l - lt); i ++)
                cout << 1 << ' ';

            for(int i = 1; i <= (r - ge); i ++)
                cout << y << ' ';
        }
    }
    return 0;
}

闫式dp分析

结果与初始化

• 结果

中序遍历为w[1 ~ n]的所有所有二叉树的最大得分，结果：f[1][n]

• 初始化为

求最大得分，所以初始化为负无穷，这里负无穷使用0来表示，当区间只有一个结点时，就只有根结点，所以f[i][i] = w[i]

细节处理

• 当根结点在左端点时，即 k = i。f[i][k - 1]是一个不合法状态，因为[i, k - 1]所表示的区间右端点比左端点大。需要特殊处理。

• 当根结点在右端点时，即 k = j。f[k + 1][j]是一个不合法状态，因为[k + 1, j]所表示的区间右端点比左端点大。需要特殊处理。

前序遍历

前序遍历的顺序时根、左、右，在计算最大得分的过程中，将每个区间对应的根结点记录，递归遍历区间时输出每个区间的根结点即可

迭代代码

#include<iostream>
#include<algorithm>
using namespace std;
const int N = 35;
int f[N][N];
int w[N];
int root[N][N];
void dfs(int l, int r){
    if(l > r) return;

    int k = root[l][r];

    printf("%d ", k);

    dfs(l, k - 1);
    dfs(k + 1, r);
}

int main(){
    int n;
    cin >> n;

    for(int i = 1; i <= n; i ++)
        cin >> w[i];

    for(int len = 1; len <= n; len ++)
        for(int i = 1; i + len - 1 <= n; i ++)
        {
            int j = i + len - 1;

            for(int k = i; k <= j; k ++)
            {
                int left = k == i ? 1 : f[i][k - 1];
                int right = k == j ? 1 : f[k + 1][j];

                int score = left * right + w[k];
                if(i == j) score = w[k];
                if(score > f[i][j])
                {
                    f[i][j] = score;
                    root[i][j] = k;
                }
            }
        }

    printf("%d\n", f[1][n]);

    dfs(1, n);

    return 0;
}

记忆化搜索

为什么不能直接递归而是记忆化搜索

图中红色的区间是需要计算的区间，计算区间可能被区间1、区间2、区间3划分出来，如果计算区间的结果没有被存储下来，那么计算区间就可能被重复计算，造成TLE，所以需要存储计算过的区间，进行剪枝优化。

#include<iostream>
#include<algorithm>
#include<cstring>
using namespace std;
const int N = 40;
int f[N][N];
int w[N];
int root[N][N];
int n;
int dfs(int l, int r){
    if(l > r) return 1;
    if(f[l][r] != -1) return f[l][r];
    if(l == r){
        f[l][r] = w[l];
        root[l][r] = l;
        return f[l][r];
    }

    for(int k = l; k <= r; k ++)
    {
        int left = dfs(l, k - 1);
        int right = dfs(k + 1, r);
        int score = left * right + w[k];
        if(score > f[l][r])
        {
            f[l][r] = score;
            root[l][r] = k;
        }
    }

    return f[l][r];
}
void pre(int l, int r){
    if(l > r) return ;

    int k = root[l][r];

    printf("%d ", k);

    pre(l, k - 1);
    pre(k + 1, r);
}
int main(){
    cin >> n;

    for(int i = 1; i <= n; i ++)
        cin >> w[i];

    memset(f, -1, sizeof f);

    dfs(1, n);
    printf("%d\n", f[1][n]);
    pre(1, n);
    return 0;
}