30pts求助,玄关
查看原帖
30pts求助,玄关
695685
AssiduousCoding楼主2024/7/18 16:22

rt

#include <bits/stdc++.h>

using namespace std;
const int N = 10010, M = 1010;

int sh, sm, eh, em, n, m;
int v[N], w[N], s[N], k;
int f[M];

int main() {
    scanf("%d:%d%d:%d%d", &sh, &sm, &eh, &em, &n);
    m = (eh - sh) * 60 + em - sm;

    for (int i = 1; i <= n; i ++ ) {
        int V, W, S;
        scanf("%d%d%d", &V, &W, &S);
        if (!S) {
            k ++ ;
            v[k] = V;
            w[k] = W;
            s[k] = -1;
        } else {
            for (int j = 1; j <= S; j <<= 1) {
                k ++ ;
                v[k] = j * V;
                w[k] = j * W;
                s[k] = 1;
                S -= j;
            }
        }
    }

    for (int i = 1; i <= k; i ++ ) {
        if (~s[i]) {
            for (int j = m; j >= v[i]; j -- )
                f[j] = max(f[j], f[j - v[i]] + w[i]);
        }
        else {
            for (int j = v[i]; j <= m; j ++ )
                f[j] = max(f[j], f[j - v[i]] + w[i]);
        }
    }

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

    return 0;
}
2024/7/18 16:22
加载中...