hrbust1053 http://acm.hrbust.edu.cn/index.php?m=ProblemSet&a=showProblem&problem_id=1053
1 #include<stdio.h> 2 #include<iostream> 3 #include<algorithm> 4 #include<string.h> 5 using namespace std; 6 struct s{ 7 int v,val; 8 }p[100005] ; 9 int dp[100002]; 10 int main() 11 { 12 int t; 13 cin>>t; 14 while(t--){ 15 memset(dp,0,sizeof(dp)); 16 int go,n; 17 cin>>go>>n; 18 for(int i=0;i<n;i++) 19 cin>>p[i].val>>p[i].v; 20 for(int i=0;i<n;i++){ 21 for(int j=p[i].v;j<=go;j++){ 22 dp[j]=max(dp[j],dp[j-p[i].v]+p[i].val); 23 } 24 } 25 26 cout<<dp[go]<<endl; 27 } 28 }