@[讨厌的狗](/user/384746) 不能压到1维吗(因为我就是一维做的doge)
by 无咕_ @ 2021-02-06 23:28:02
@[讨厌的狗](/user/384746)
```cpp
for(int j=1;j<=2;j++)
```
这是个啥意思?不是应该枚举到t吗?
然后这里
```cpp
dp[i][j] = max(dp[i-1][j],dp[i-1][j-value[i]] + value[i]);
```
不应该是
```cpp
dp[i][j] = max(dp[i-1][j],dp[i-1][j-time[i]] + value[i]);
```
吗?
by 林聪 @ 2021-02-07 00:07:10
@[林聪](/user/69796)
谢谢Thanks♪(・ω・)ノ
by JRE3 @ 2021-02-07 11:11:25
@[林聪](/user/69796)
按你的方法改后,似乎还有点问题,WA了六个
```cpp
#include <bits/stdc++.h>
using namespace std;
int dp[2000][2000];
int main(){
int time[2000] = {0}; // 时间
int value[2000] = {0}; // 价值
memset(dp,0,sizeof(dp));
int t,m = 0; // 最大采药时间和草药数量
cin >> t >> m;
for(int i=1;i<=m;i++){
cin >> time[i] >> value[i];
}
for(int i=1;i<=m;i++){
for(int j=1;j<=t;j++){
if(time[i] > j){
dp[i][j] = dp[i][j-1];
}
else{
dp[i][j] = max(dp[i-1][j],dp[i-1][j-time[i]] + value[i]);
}
}
}
cout << dp[m][t];
return 0;
}
```
by JRE3 @ 2021-02-07 11:44:18
@[讨厌的狗](/user/384746)
这个转移还是有问题的吧:
```cpp
if(time[i] > j){
dp[i][j] = dp[i][j-1];
}
```
不应该是:
```cpp
if(time[i] > j){
dp[i][j] = dp[i-1][j];
}
```
就意思是不取
by 林聪 @ 2021-02-07 16:03:39
@[林聪](/user/69796) 大感谢,全WA了
by JRE3 @ 2021-02-07 20:29:50
@[讨厌的狗](/user/384746) soory打错字了,全AC
by JRE3 @ 2021-02-07 20:31:19
@[讨厌的狗](/user/384746) 我们好像撞头像了(
![](https://xn--wcs.tk/j)
by MichaelDickson @ 2022-01-09 21:02:21