POJ 3211 Washing Clothes

  

   

    

     

    
    

     

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

    

     

    
    

     

      Problem: POJ 3211 Washing Clothes
     
    
   

    

     

    
    

     

      Time: 16MS
     
    
   

    

     

    
    

     

      Memory: 232K
     
    
   

    

     

    
    

     

      Accepted Time: 2009-08-05 13:25:10
     
    
   

    

     

    
    

     

      Tip: 转化为01背包问题 http://www.cppblog.com/gzwzm06/articles/81753.html
     
    
   

    

     

    
    

     

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

    

     

    
    

     

      #include <stdio.h>
     
    
   

    

     

    
    

     

      #include <string.h>
     
    
   

    

     

    
    

     

      int main()
     
    
   

    

     

    
    

     

      {
     
    
   

    

     

    
    

     
	int n,m,i,j,k;
     
    
   

    

     

    
    

     
	int a[10][100],c[10],d[10];
     
    
   

    

     

    
    

     
	char b[10][10];
     
    
   

    

     

    
    

     
	while(1)
     
    
   

    

     

    
    

     

      	{
     
    
   

    

     

    
    

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

    

     

    
    

     
		if(n+m==0)break;
     
    
   

    

     

    
    

     
		memset(c,0,sizeof(c));
     
    
   

    

     

    
    

     
		memset(d,0,sizeof(d));
     
    
   

    

     

    
    

     
		for(i=0;i<n;i++)scanf("%s",b[i]);
     
    
   

    

     

    
    

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

    

     

    
    

     

      		{
     
    
   

    

     

    
    

     
			int t1;
     
    
   

    

     

    
    

     
			char t2[10];
     
    
   

    

     

    
    

     
			scanf("%d%s",&t1,t2);
     
    
   

    

     

    
    

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

    

     

    
    

     
			if(strcmp(t2,b[j])==0)break;
     
    
   

    

     

    
    

     

      			a[j][c[j]++]=t1;
     
    
   

    

     

    
    

     

      			d[j]+=t1;
     
    
   

    

     

    
    

     

      		}
     
    
   

    

     

    
    

     
		int sum=0;
     
    
   

    

     

    
    

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

    

     

    
    

     

      		{
     
    
   

    

     

    
    

     
			bool dp[100009];
     
    
   

    

     

    
    

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

    

     

    
    

     

      			dp[0]=1;
     
    
   

    

     

    
    

     
			int t1=0,t2=d[i]>>1;
     
    
   

    

     

    
    

     
			for(j=0;j<c[i];j++)
     
    
   

    

     

    
    

     
 for(k=t2;k>=a[i][j];k--)//01背包 
     
    
   

    

     

    
    

     

       {
     
    
   

    

     

    
    

     
 if(dp[k-a[i][j]])
     
    
   

    

     

    
    

     

       {
     
    
   

    

     

    
    

     

       dp[k]=1;
     
    
   

    

     

    
    

     
 if(k>t1)t1=k;
     
    
   

    

     

    
    

     

       }
     
    
   

    

     

    
    

     

       }
     
    
   

    

     

    
    

     

      			sum+=d[i]-t1;
     
    
   

    

     

    
    

     

      		}
     
    
   

    

     

    
    

     
		printf("%d/n",sum);
     
    
   

    

     

    
    

     

      	}
     
    
   

    

     

    
    

     
	return 0;
     
    
   

    

     

    
    

     

      }
     
    
  
 

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

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