题意：01背包，要求第k优解； 求第k优解就好比要比较两个班的前十名推出全年级全十，需要将选与不选所有的结果记下来比较；
#include<iostream> #include<algorithm> #include<string> #include<cstring> #include<map> #include<queue> #include<cmath> #include<stack> #include<vector> #include<cstdio> #define MAXN 33000 #define INF 0x3f3f3f3f #define lmid l,m,rt<<1 #define rmid m+1,r,rt<<1|1 #define ls rt<<1 #define rs rt<<1|1 #define Mod 1000000007 #define i64 __int64 using namespace std; int dp[1005][35],x[105],y[105],a[105],b[105]; int main() { int t; scanf("%d",&t); while(t--) { int n,m,k; scanf("%d%d%d",&n,&m,&k); for(int i=0;i<n;i++) scanf("%d",&x[i]); for(int i=0;i<n;i++) scanf("%d",&y[i]); memset(dp,0,sizeof(dp)); for(int i=0;i<n;i++) for(int j=m;j>=y[i];j--) { for(int l=1;l<=k;l++) { a[l]=dp[j-y[i]][l]+x[i]; b[l]=dp[j][l]; } a[k+1]=b[k+1]=-1; int w,e,r; w=e=r=1; while(w<=k&&(a[e]!=-1||b[r]!=-1)) { if(a[e]>b[r]) dp[j][w]=a[e],++e; else dp[j][w]=b[r],++r; if(dp[j][w]!=dp[j][w-1]) ++w; } } cout<<dp[m][k]<<endl; } }