题解 | #[NOIP2006]开心的金明#

#include<bits/stdc++.h>

using namespace std;

typedef long long ll;
const int N=30010;
ll dp[26][N];
struct ty{
    int v,imp;
    ll sum;
}a[N];

int main()
{
    int N,m;
    cin >> N >> m;
    for(int i=1;i<=m;i++){
        cin >> a[i].v >> a[i].imp;
        a[i].sum=a[i].v*a[i].imp;
    }
    dp[0][0]=0;
    for(int i=1;i<=m;i++){
        for(int j=0;j<=N;j++){
            if(a[i].v>j){
                dp[i][j]=dp[i-1][j];
            }else{
                dp[i][j]=max(dp[i-1][j],dp[i-1][j-a[i].v]+a[i].sum);
            }
        }
    }
    cout << dp[m][N]; 
}