数组开小了,这题必须用滚动数组优化到一维
by Z3k7223 @ 2024-02-04 10:35:40
@[Z3k7223](/user/794083) o,可是蒟蒻不会滚动数组
by ZBXALQX @ 2024-02-04 10:38:45
@[Z3k7223](/user/794083)
```cpp
#include<bits/stdc++.h>
using namespace std;
const int N=2010,M=10001;
int n,w[N],c[N];
long long m,f[M];
int main(){
scanf("%d%d",&m,&n);
for(int i=1;i<=n;i++){
scanf("%d%d",&w[i],&c[i]);
}
for(int i=1;i<=n;i++){
for(int j=w[i];j<=m;j++){
f[i]=f[i-1];
f[i]=max(f[i],f[i-w[i]]+c[i]);
}
}
printf("%d",f[n]);
return 0;
}
```
这样子答案会变成3
by ZBXALQX @ 2024-02-04 10:41:12
```
for (int i = 1; i <= n; i++) {
for (int j = v[i]; j <= m; j++) {
f[j] = max(f[j], (long long)f[j - v[i]] + w[i]);
}
}
```
by Z3k7223 @ 2024-02-04 10:42:07
循环长这样
by Z3k7223 @ 2024-02-04 10:42:29
@[Z3k7223](/user/794083) 不对啊
by ZBXALQX @ 2024-02-04 10:44:46
@[ZBXALQX](/user/1070547) v是体积(时间),w是价值
by Z3k7223 @ 2024-02-04 10:45:38
还带了点绿
by jiangyunuo @ 2024-02-04 10:50:28
@[Z3k7223](/user/794083)
```cpp
#include<bits/stdc++.h>
using namespace std;
const int N=19999;
long long m,f[N],n,w[N],c[N];
int main(){
scanf("%d%d",&m,&n);
for(int i=1;i<=n;i++){
scanf("%d%d",&w[i],&c[i]);
}
for(int i=1;i<=n;i++){
for(int j=w[i];j<=m;j++){
f[j]=f[j-1];
f[j]=max(f[j],f[j-w[i]]+c[i]);
}
}
printf("%d",f[m]);
return 0;
}
```
[万紫千红总是春不一样了](https://www.luogu.com.cn/record/146053753)
by ZBXALQX @ 2024-02-04 10:51:51
@[jiangyunuo](/user/1061050) 没写你说什么
by ZBXALQX @ 2024-02-04 10:52:45