讨论 / 不完美的题解
Snake52996 2017-10-22 05:48:29
点我顶贴 收藏 删除
因为题目数据范围不大,可以直接动态规划,甚至不需要优化.

#include<iostream>

#include<cmath>

using namespace std;

const int MAX=30;

int v[MAX],p[MAX];

int n,m;

int dg(int i,int sum)

{

if(i>=m) return 0;

if(sum+v[i]>n) return dg(i+1,sum);

return max(dg(i+1,sum+v[i])+v[i]*p[i],dg(i+1,sum));

}

int main()

{

cin>>n>>m;

for(int i=0;i<m;i++) cin>>v[i]>>p[i];

cout<<dg(0,0);

return 0;

}

查看更多回复
提交回复