题解 | 【模板】二维费用背包

/*我遇到的动态规划问题不多，只能先利用0,1背包问题的初级解法来看，设置dp[n + 1][T + 1][H + 1]数组，三个维度上有一维是0则整体的值为0，这在初始化时候要做到，之后就是为数组赋值了，这里用到3层循环
dp数组的赋值逻辑是：if(event[i - 1][0] <= j && event[i - 1][1] <= k){
                    dp[i][j][k] = max(dp[i - 1][j][k], event[i - 1][2] + dp[i - 1][j - event[i - 1][0]][k - event[i - 1][1]]);
                }
                else{
                    dp[i][j][k] = dp[i - 1][j][k];
                }

*/
#include <stdio.h>
#include <stdlib.h>

//max函数
long long max(long long a, long long b){
    return a > b ? a : b;
}

int main(){
    //读取数据

    int n;
    scanf("%d\n", &n);
    int T, H;
    scanf("%d %d\n", &T, &H);
    
    long long **event = (long long **)malloc(sizeof(long long *) * n);
    for(int i = 0; i < n; i++){
        event[i] = (long long *)malloc(sizeof(long long) *3);
        scanf("%lld %lld %lld\n", event[i], event[i] + 1, event[i] + 2);
    }

    //设置并初始化dp数组
    long long ***dp = (long long ***)malloc(sizeof(long long ***) * (n + 1));
    for(int i = 0; i < n + 1; i++){
        dp[i]= (long long **)malloc(sizeof(long long **) * (T + 1));
        for(int j = 0; j < T + 1; j++){
            dp[i][j] = (long long *)malloc(sizeof(long long) * (H + 1));
        }
    }
    for(int i = 0; i < T + 1; i++){
        for(int j = 0; j < H + 1; j++){
            dp[0][i][j] = 0;
        }
    }
    for(int i = 0; i < n + 1; i++){
        for(int j = 0; j < H + 1; j++){
            dp[i][0][j] = 0;
        }
    }
    for(int i = 0; i < n + 1; i++){
        for(int j = 0; j < T + 1; j++){
            dp[i][j][0] = 0;
        }
    }

    //为dp数组赋值
    for(int i = 1; i < n + 1; i++){
        for(int j = 1; j < T + 1; j++){
            for(int k = 1; k < H + 1; k++){
                //状态转移方程实现
                if(event[i - 1][0] <= j && event[i - 1][1] <= k){
                    dp[i][j][k] = max(dp[i - 1][j][k], event[i - 1][2] + dp[i - 1][j - event[i - 1][0]][k - event[i - 1][1]]);
                }
                else{
                    dp[i][j][k] = dp[i - 1][j][k];
                }
                }
            }
        }

    //输出结果
    printf("%lld\n", dp[n][T][H]);

    //逐层释放空间
    for(int i = 0; i < n; i++){
        free(event[i]);
    }
    free(event);

    for(int i = 0; i < n + 1; i++){
        for(int j = 0; j < T + 1; j ++){
            free(dp[i][j]);
        }
        free(dp[i]);
    }
    free(dp);

    
    return 0;
}