Skip to content

13030: 【原3030】mushroom

题目

题目描述

author: mushroom 原OJ链接:https://acm.sjtu.edu.cn/OnlineJudge-old/problem/3030

【问题描述】

从前有座山,山上有座庙,庙里有个老和尚,老和尚让小和尚采蘑菇... “采蘑菇是一门博大精深的学问”老和尚如是说。 采摘不同的蘑菇,需要不同的时间;采集不同的蘑菇,有不同的价值。 小和尚苦恼地揉了揉眉心,他想要在规定地时间中,采集价值最大地蘑菇,却苦无良策, 只能打电话询问正在学习编程的你,期望你能帮他解决这个问题。

【输入文件】

输入的第一行有两个整数T(1 <= T <= 1000)和M(1 <= M <= 100),用一个空格隔开,T代表总共能够用来采蘑菇的时间,M代表山里的磨菇的数目。接下来的M行每行包括两个在1到100之间(包括1和100)的整数,分别表示采摘某磨菇的时间和磨菇的价值。

【输出文件】

输出在规定的时间内,可以采到的磨菇的最大总价值。

【样例输入】

100 4
99 100
101 1
97 3
2 3

【样例输出】

100

【数据规模】

对于30%的数据,M <= 10; 对于全部的数据,M <= 100。

BugenZhao's solution

//
// Created by BugenZhao on 2019/3/23.
//

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>

using namespace std;

using ll=long long;

class MushRoom {
public:
    int t;
    int v;
};

int main() {
    MushRoom ms[105];
    int T, M;
    cin >> T >> M;
    int a, b;
    for (int i = 1; i <= M; ++i) {
        scanf("%d%d", &ms[i].t, &ms[i].v);
    }
    int values[1005]{};
    for (int i = 1; i <= M; ++i) {
        for (int j = T; j >= ms[i].t; --j) {
            values[j] = max(values[j], values[j - ms[i].t] + ms[i].v);
        }
    }

    cout << values[T] << endl;
    return 0;
}

FineArtz's solution

/* mushroom */
#include <iostream>
using namespace std;

int main(){
    int f[1005] = {0};
    int T, M;
    cin >> T >> M;
    int t[105], w[105];
    for (int i = 1; i <= M; ++i)
        cin >> t[i] >> w[i];
    for (int i = 1; i <= M; ++i){
        for (int j = T; j >= t[i]; --j)
            f[j] = max(f[j], f[j - t[i]] + w[i]);
    }
    cout << f[T] << endl;
    return 0;
}

ligongzzz's solution

#include "iostream"
#include "cstdio"
using namespace std;

int time_val[109], val[109];
int dp_data[109][1009] = { 0 };

int dp(int num, int v) {
    if (num == 0)
        return 0;
    if (dp_data[num][v] > 0)
        return dp_data[num][v];
    if (time_val[num - 1] > v) {
        dp_data[num][v] = dp(num - 1, v);
        return dp_data[num][v];
    }
    else {
        int ans1 = dp(num - 1, v), ans2 = dp(num - 1, v - time_val[num - 1]) + val[num - 1];
        dp_data[num][v] = ans1 > ans2 ? ans1 : ans2;
        return dp_data[num][v];
    }
}

int main() {
    int T, M;
    cin >> T >> M;

    for (int i = 0; i < M; ++i)
        scanf("%d %d", &time_val[i], &val[i]);

    cout << dp(M, T);

    return 0;
}

skyzh's solution

#include <iostream>
using namespace std;


int main() {
    int T, M;
    int dp[100][1002];
    int val[100];
    int t[100];
    cin >> T >> M;
    for (int i = 0; i < M; i++) cin >> t[i] >> val[i];
    for (int i = 0; i < M; i++) {
        for (int j = 0; j <= 1000; j++) {
            dp[i][j] = -1;
        }
    }
    dp[0][0] = 0;
    dp[0][t[0]] = val[0];

    for (int i = 1; i < M; i++) {
        for (int j = 0; j <= T; j++) {
            int res = -1;
            if (dp[i - 1][j] != -1) {
                res = dp[i - 1][j];
            }
            if (j - t[i] >= 0 && dp[i - 1][j - t[i]] != -1) {
                res = max(res, dp[i - 1][j - t[i]] + val[i]);
            }
            dp[i][j] = res;
        }
    }
    int res = 0;
    for (int j = 0; j <= T; j++) {
        res = max(res, dp[M - 1][j]);
    }
    cout << res << endl;
    return 0;
}

yyong119's solution

#include <cstdio>
#include <cstring>
#include <algorithm>
#define MAX_T 1010
#define MAX_M 105
using namespace std;
int t, m;
struct Node {
    int time, value;
} a[MAX_M];
int f[MAX_T];
inline int read() {
    char ch = getchar(); int res = 0, flag = 1;
    while (ch != '-' && (ch < '0' || ch > '9')) ch = getchar();
    if (ch == '-') flag = -1, ch = getchar();
    while (ch >= '0' && ch <= '9') res = res * 10 + ch - '0', ch = getchar();
    return res * flag;
}
int main() {
    t = read(); m = read();
    for (register int i = 0; i < m; ++i)
        a[i].time = read(), a[i].value = read();
    for (register int i = 0; i < m; ++i)
        for (register int j = t; j >= a[i].time; --j)
                f[j] = max(f[j], f[j - a[i].time] + a[i].value);

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