AcWing 426. 开心的金明
原题链接
简单
作者:
把这题一顿爆刷
,
2021-02-09 12:13:24
,
所有人可见
,
阅读 291
DP 背包问题
C++ 代码
#include <iostream>
#include <algorithm>
using namespace std;
const int N = 30010, M = 30;
int n,m;
int f[M][N];
int main(){
cin >> n >> m;
for(int i=1; i<=m; i++){
int v,w;
cin >> v >> w;
w *= v;
for(int j=0; j<=n; j++){
f[i][j] = f[i-1][j];
if(j - v >=0){
f[i][j] = max(f[i][j],f[i-1][j-v] + w);
}
}
}
cout << f[m][n];
return 0;
}
优化空间后
#include <iostream>
#include <algorithm>
using namespace std;
const int N = 30010;
int n,m;
int f[N];
int main(){
cin >> n >> m;
for(int i=1; i<=m; i++){
int v,w;
cin >> v >> w;
w *= v;
for(int j=n; j>=v; j--){
f[j] = max(f[j],f[j-v] + w); // f[i][j] = max(f[i-1][j],f[i-1][j-v] + w) 从大到小算才是这样
}
}
cout << f[n];
return 0;
}