HEU 5011 Max Use Of CPU

  

   

    

     

    
    

     

      /***********************************
     
    
   

    

     

    
    

     

      Problem: HEU 5011 Max Use Of CPU
     
    
   

    

     

    
    

     

      Time: 0.0020 s
     
    
   

    

     

    
    

     

      Memory: 536 k
     
    
   

    

     

    
    

     

      Accepted Time: 2009-08-05 19:26:45
     
    
   

    

     

    
    

     

      Tip: 
     
    
   

    

     

    
    

     

      ************************************/
     
    
   

    

     

    
    

     

      #include <stdio.h>
     
    
   

    

     

    
    

     

      #include <string.h>
     
    
   

    

     

    
    

     

      int main()
     
    
   

    

     

    
    

     

      {
     
    
   

    

     

    
    

     
	int Case;
     
    
   

    

     

    
    

     
	scanf("%d",&Case);
     
    
   

    

     

    
    

     
	while(Case--)
     
    
   

    

     

    
    

     

      	{
     
    
   

    

     

    
    

     
		int n,t,i,j,a,dp[15000];
     
    
   

    

     

    
    

     
		scanf("%d%d",&n,&t);
     
    
   

    

     

    
    

     
		for(int i=0;i<=t;i++)dp[i]=-1;
     
    
   

    

     

    
    

     

      		dp[0]=0;
     
    
   

    

     

    
    

     
		for(i=0;i<n;i++)
     
    
   

    

     

    
    

     

      		{
     
    
   

    

     

    
    

     
			scanf("%d",&a);
     
    
   

    

     

    
    

     
			for(j=t;j>=a;j--)
     
    
   

    

     

    
    

     

      			{
     
    
   

    

     

    
    

     
 if(dp[j-a]!=-1&&dp[j]<dp[j-a]+1)//加入dp[j]<dp[j-a]+1限制 
     
    
   

    

     

    
    

     

       {
     
    
   

    

     

    
    

     

       dp[j]=dp[j-a]+1;
     
    
   

    

     

    
    

     
 //因为有最大CPU时间的限制，所以不能在此循环中寻找最大任务数
     
    
   

    

     

    
    

     

       }
     
    
   

    

     

    
    

     

      			}
     
    
   

    

     

    
    

     

      		}
     
    
   

    

     

    
    

     
		int max1=-1,max2=-1;
     
    
   

    

     

    
    

     
		for(i=t;i>=0;i--)
     
    
   

    

     

    
    

     

      		{
     
    
   

    

     

    
    

     
			if(max1<dp[i])
     
    
   

    

     

    
    

     

      			{
     
    
   

    

     

    
    

     

       max1=dp[i];
     
    
   

    

     

    
    

     

       max2=i;
     
    
   

    

     

    
    

     

      			}
     
    
   

    

     

    
    

     

      		}
     
    
   

    

     

    
    

     
		printf("%d %d/n",max1,max2);
     
    
   

    

     

    
    

     

      	}
     
    
   

    

     

    
    

     
	return 0;
     
    
   

    

     

    
    

     

      }
     
    
  
 

文章来源: blog.csdn.net，作者：万猫学社，版权归原作者所有，如需转载，请联系作者。

原文链接：blog.csdn.net/heihaozi/article/details/4417231