POJ 1837 Balance

  

   

    

     

    
    

     

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

    

     

    
    

     

      Problem: POJ 1837 Balance
     
    
   

    

     

    
    

     

      Time: 16MS
     
    
   

    

     

    
    

     

      Memory: 748K
     
    
   

    

     

    
    

     

      Accepted Time: 2009-08-05 15:56:57
     
    
   

    

     

    
    

     

      Tip: http://www.cppblog.com/guyuecanhui/articles/88193.html
     
    
   

    

     

    
    

     

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

    

     

    
    

     

      #include <stdio.h>
     
    
   

    

     

    
    

     

      #include <string.h>
     
    
   

    

     

    
    

     

      #define MAX 7500
     
    
   

    

     

    
    

     

      int main()
     
    
   

    

     

    
    

     

      {
     
    
   

    

     

    
    

     
	int c,g,hook[21],weight[21],dp[21][MAX+1],i,j,k;
     
    
   

    

     

    
    

     
	while(scanf("%d%d",&c,&g)!=EOF)
     
    
   

    

     

    
    

     

      	{
     
    
   

    

     

    
    

     
		for(i=0;i<c;i++)scanf("%d",&hook[i]);
     
    
   

    

     

    
    

     
		for(i=0;i<g;i++)scanf("%d",&weight[i]);
     
    
   

    

     

    
    

     
		memset(dp,0,sizeof(dp));
     
    
   

    

     

    
    

     
		for(i=0;i<c;i++)dp[1][weight[0]*hook[i]+MAX/2]++;
     
    
   

    

     

    
    

     
		for(i=1;i<g;i++)
     
    
   

    

     

    
    

     
		for(j=0;j<c;j++)
     
    
   

    

     

    
    

     
		for(k=0;k<=MAX;k++)
     
    
   

    

     

    
    

     
		if(dp[i][k])dp[i+1][k+weight[i]*hook[j]]+=dp[i][k];
     
    
   

    

     

    
    

     
		printf("%d/n",dp[g][MAX/2]);
     
    
   

    

     

    
    

     

      	}
     
    
   

    

     

    
    

     
	return 0;
     
    
   

    

     

    
    

     

      }
     
    
  
 

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

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