lshstc 2017-04-12 19:08:20
点我顶贴
收藏
删除
#include <iostream>
using namespace std;
int N,m;
int v[30001],p[30001];
int dp[30001];
void init(){
int i;
cin>>N>>m;
for(i=1;i<=m;i++){
cin>>v[i]>>p[i];
}
}
void genius01dp(){
int i,j;
for(i=1;i<=m;i++){
for(j=N;j>=v[i];j--){
dp[j]=max(dp[j],dp[j-v[i]]+v[i]*p[i]);
}
}
cout<<dp[N];
}
int main(){
init();
genius01dp();
return 0;
}