code jam round 1A 2022 weightlifting 规划练习间的器材摆放顺序

1、分治

2、记忆化

3、动态规划

https://codingcompetitions.withgoogle.com/codejam/round/0000000000877ba5/0000000000aa9280#problem

#include 
using namespace std;

int solve(vector> V)
{
    int N = V.size(), M = V[0].size();
    vector> DP(N, vector(N, -1));//练习i-j的器材添加次数（=取下次数）

    function solve = [&](int f, int t)
    {
        if (DP[f][t] != -1)
            return DP[f][t];
        if (f == t)
        {
            int x = 0;
            for (auto v : V[f])
                x += v;
            return DP[f][t] = x;
        }
        vector mn(M, INT_MAX);
        for (int i = f; i <= t; i++)
            for (int j = 0; j < M; j++)
                mn[j] = min(mn[j], V[i][j]);

        int bs = 0;
        for (int x : mn)
            bs += x;

        int mnv = INT_MAX;
        for (int i = f; i < t; i++)
            mnv = min(mnv, solve(f, i) + solve(i + 1, t));

        return DP[f][t] = mnv - bs;//第二段可以从bs开始而非0
    };

    return 2 * solve(0, N - 1);
}

int main()
{
    int T;
    scanf("%d", &T);
    for (int tc = 1; tc <= T; tc++)
    {
        int N, M;
        scanf("%d%d", &N, &M);
        vector> V(N, vector(M));
        for (auto &y : V)
            for (int &x : y)
                scanf("%d", &x);
        printf("Case #%d: %d\n", tc, solve(V));
    }
}

题解引用自 HYEA