讨论 / c++ 动规 AC100
silentrain 2017-11-18 10:28:45
点我顶贴 收藏 删除
#include <iostream>

#include <cstring>

#define max(a,b) a>b?a:b

using namespace std;

int main(){

int n,m;

cin>>n>>m;

int v[m+1],p[m+1],a[m+1];

for(int i=1;i<=m;i++){

cin>>v[i]>>p[i];

a[i]=v[i]*p[i];

}

int dp[m+1][n+1];

memset(dp,0,sizeof(dp));

for(int i=1;i<=m;i++){

for(int j=0;j<=n;j++){

if(j>=v[i]){

dp[i][j]=max(dp[i-1][j],dp[i-1][j-v[i]]+a[i]);

}else{

dp[i][j]=dp[i-1][j];

}

}

}

cout<<dp[m][n];

return 0;

}

#1 Gemengmeng@2018-01-04 23:33:52
回复 删除
厉害
查看更多回复
提交回复