NYOJ 49---开心的小明

点击打开链接NYOJ 49

题目： 开心的小明

#include <algorithm>#include <iostream>#include <cstring>#include <string>#include <vector>#include <cstdio>#include <stack>#include <queue>#include <cmath>#include <set>using namespace std;#define MAXN 100010int t , n , m;int w[MAXN] , v[MAXN];int dp[MAXN];int max(int a , int b){ return a>b?a:b;}void solve() { int i , j; memset(dp , 0 , sizeof(dp)); for(i = 0 ; i < m ; i++){ for(j = n ; j >= 0 ; j--){ if(j >= w[i]){ dp[j] = max(dp[j-w[i]]+v[i] , dp[j]); } } } printf("%d\n" , dp[n]);}int main() { //freopen("input.txt" , "r" , stdin); int a , b; scanf("%d%*c" , &t); while(t--){ scanf("%d%d*c" , &n , &m); for(int i = 0 ; i < m ; i++){ scanf("%d%d*c" , &a , &b); w[i] = a ; v[i] = a*b; } solve(); } return 0;}