closefrom

这题是一个背包。。。

令f[i]表示花费i元钱能达到的最大的物品与价格的乘积的总和

所以就有 f[i]=max{f[i],f[i-v[j]]+v[i]*w[i]}

//My Code：
#include <cstdio>
#include <algorithm>
using namespace std;
int n,m,fm[30005];
struct node{
    int v,p;
}mm[30];
bool cp(node a,node b){
    if(a.p!=b.p)return a.p>b.p;
    else return a.v<b.v;
}
int max(int a,int b){return a>b?a:b;}
int main(){
    scanf("%d%d",&n,&m);
    for(int i=1;i<=m;i++)scanf("%d%d",&mm[i].v,&mm[i].p);
    sort(mm+1,mm+m+1,cp);
    for(int i=1;i<=m;i++){
        for(int j=n;j>=mm[i].v;j--){
            fm[j]=max(fm[j],fm[j-mm[i].v]+mm[i].v*mm[i].p);
        }
    }
    printf("%d",fm[n]);
    return 0;
}