题目意思就是小xc想送给幼儿园女孩子们每人一座城堡，这些城堡都是用立方体的积木搭成，现在为了不出现偏袒那个女生的现象，必须要求送给每个女孩子的城堡的告诉都一样高，那么小xc想出来的办法就是在抽掉其中部分城堡当中的积木，尽量让所有的城堡能达到最大公共高度。
那么其实转念一想就很简单，其实就是把其中每个塔的积木全部当做是物品，求这些物品尽量能占得的最大空间，然后求所有城堡的能到达的最大公共高度。
View Code 1 #include<iostream> 2 #include<stdio.h> 3 using namespace std; 4 int dp[110][10000],Count[10000]; 5 int main() 6 { 7 int n,height,Minvalue,sum; 8 while(scanf("%d",&n)!=EOF) 9 { 10 Minvalue=100000; 11 memset(dp,0,sizeof(dp)); 12 memset(Count,0,sizeof(Count)); 13 for(int i=0;i<n;i++) 14 { 15 dp[i][0]=1,height=1,sum=0; 16 while(1) 17 { 18 scanf("%d",&height); 19 if(height==-1)break; 20 sum+=height; 21 for(int j=sum;j>=height;j--) 22 { 23 if(dp[i][j-height]==1&&dp[i][j]==0) 24 { 25 dp[i][j]=1; 26 Count[j]++; 27 } 28 } 29 } 30 Minvalue=sum<Minvalue?sum:Minvalue; 31 } 32 int answer; 33 for(answer=Minvalue;answer>0;answer--) 34 if(Count[answer]==n)break; 35 printf("%d\n",answer); 36 } 37 return 0; 38 } 39
转载于:https://www.cnblogs.com/nuoyan2010/archive/2012/09/01/2667083.html
