linchenzhi 2018-12-10 05:50:36
点我顶贴
收藏
删除
#include<bits/stdc++.h>
using namespace std;
int n,m;
int p[1001];
int v[1001];
int f[1001][1001];
int main()
{
cin>>n>>m;
for(int i=1;i<=m;i++)
{
cin>>v[i]>>p[i];
}
for(int i=1;i<=m;i++)
{
for(int j=n;j>=0;j--)
{
if(v[i]<j)
{
f[i][j]=max(f[i-1][j],f[i-1][j-v[i]]+p[i]*v[i]); // 状态转移方程!
}
else f[i][j]=f[i-1][j];
}
}
cout<<f[m][n];
}