# 13030: 【原3030】mushroom

### 题目描述

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

## 【样例输入】

``````100 4
99 100
101 1
97 3
2 3
``````

## 【样例输出】

``````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];
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() {