类似于poj 1014 qduoj
#include<bits/stdc++.h> #define maxn 100007 using namespace std; int mm[20][20]; int dp[maxn]; int v[maxn]; int w[maxn]; int main() { int n,m,t; scanf("%d",&t); while(t--) { scanf("%d%d",&n,&m); memset(mm,0,sizeof(mm)); memset(dp,0,sizeof(dp)); int ti,vi; for(int i=0;i<n;i++) { scanf("%d%d",&ti,&vi); mm[ti][vi]++; } int cnt=1; for(int i=1;i<=10;i++) for(int j=1;j<=10;j++) { int tmp = mm[i][j]; for(int k=1;k<=tmp;k<<=1) { v[cnt]=j*k; w[cnt]=i*k; cnt++; tmp-=k; } if(tmp>0) { v[cnt]=j*tmp; w[cnt]=i*tmp; cnt++; } } for(int i=1;i<cnt;i++) for(int j=m;j>=w[i];j--) dp[j]=max(dp[j-w[i]]+v[i],dp[j]); cout<<dp[m]<<endl; } return 0; }