肯定超时啊。正解不是dp么
by 老子是北瓜 @ 2021-07-07 20:14:24
终于可以了
```cpp
#include <bits/stdc++.h>
using namespace std;
int t, m;
int dp[10005][105] = {0};
struct S{
int t;
int v;
}s[105];
int f(int time, int i = 0){
if(i == m)
return 0;
int n1;
if(!dp[time][i+1])
dp[time][i+1] = f(time, i+1);
n1 = dp[time][i+1];
int n2 = n1;
if(time-s[i].t >= 0){
if(!dp[time-s[i].t][i+1])
dp[time-s[i].t][i+1] = f(time-s[i].t, i+1);
n2 = dp[time-s[i].t][i+1]+s[i].v;
}
return n1 > n2? n1: n2;
}
int main(){
cin >> t >> m;
for(int i = 0; i < m; i++)
cin >> s[i].t >> s[i].v;
cout << f(t);
return 0;
}
```
by Radia @ 2021-07-07 20:42:17