题解 | 毕业bg

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

void Swap(int *a,int *b){
    int tmp=*a;
    *a=*b;
    *b=tmp;
}

void Sort(int bg[][3],int n){
    int i,j,k,t1,t2,t3;
    for(i=1;i<=n;i++){
        k=i;
        for(j=i+1;j<=n;j++){
            if(bg[j][2]<bg[k][2])
            k=j;
        }
        if(k!=i){
            Swap(&bg[i][0], &bg[k][0]);
            Swap(&bg[i][1], &bg[k][1]);
            Swap(&bg[i][2], &bg[k][2]);
        }
    }
}
void Print(int *dp[],int n,int mt){
    int i=0,j=0;
    printf("dp is:\n");
    for(;i<=n;i++){
        for(j=0;j<=mt;j++)
            printf("%d ",dp[i][j]);
        printf("\n");
    }
}
int main() {
    int n,i,j,bg[31][3],mt;
    while (scanf("%d", &n) != EOF) { // 注意 while 处理多个 case
        // 64 位输出请用 printf("%lld") to
        if(n<0)
        break;
        mt=0;
        for(i=1;i<=n;i++){
            scanf("%d%d%d",&bg[i][0],&bg[i][1],&bg[i][2]);
            if(bg[i][2]>mt)
            mt=bg[i][2];//最晚离场的发起人的离场时间
        }
        Sort(bg, n);
        int **dp=(int **)calloc(n+1,sizeof(int*));
        for (i=0; i<=n; i++) {
            dp[i]=(int *)calloc(mt+1,sizeof(int));
        }
        for(i=1;i<=n;i++){
            for(j=1;j<=mt;j++){
                if(j>bg[i][2]){
                    dp[i][j]=dp[i][j-1];
                }
                else if(bg[i][1]<=j){
                    if(dp[i-1][j-bg[i][1]]+bg[i][0]>dp[i-1][j])
                    dp[i][j]=dp[i-1][j-bg[i][1]]+bg[i][0];
                    else
                     dp[i][j]=dp[i-1][j];
                }
                else {
                    dp[i][j]=dp[i-1][j];
                }
            }
        }
        //Print(dp,n,mt);
        printf("%d\n", dp[n][mt]);
        for (i=0; i<=n; i++) {
            free(dp[i]);
        }
        free(dp);
    }
    return 0;
}