Time Limit: 5000/2000 MS (Java/Others) Memory
Limit: 32768/32768 K (Java/Others)
Total Submission(s):
1842 Accepted Submission(s): 952
1 #include<stdio.h> 2 #include<string.h> 3 #include<algorithm> 4 using namespace std; 5 int f[1020][1020]; 6 int main() 7 { 8 int i,j,n,k,m,t,tt,v[1020],va[1020],tmp[1020],cnt,x; 9 scanf("%d",&t); 10 while(t--) 11 { 12 scanf("%d%d%d",&n,&m,&tt); 13 for(i=1; i<=n; i++) 14 scanf("%d",&va[i]); 15 for(i=1; i<=n; i++) 16 scanf("%d",&v[i]); 17 memset(f,0,sizeof(f)); 18 for(i=1; i<=n; i++) 19 { 20 for(j=m; j>=v[i]; j--) 21 { 22 cnt=0; 23 memset(tmp,0,sizeof(tmp)); 24 for(k=1;k<=tt;k++) 25 { 26 tmp[cnt++]=f[j][k]; 27 tmp[cnt++]=f[j-v[i]][k]+va[i]; 28 } 29 sort(tmp,tmp+cnt); 30 x=1; 31 for(k=cnt-1;k>=0;k--) 32 { 33 if(x>tt) 34 break; 35 if(k==cnt-1||tmp[k]!=tmp[k+1]) 36 f[j][x++]=tmp[k]; 37 } 38 } 39 } 40 printf("%d\n",f[m][tt]); 41 } 42 return 0; 43 }
原文:http://www.cnblogs.com/lxm940130740/p/3572538.html