题解:背包方案总数问题,就对于每一个城堡,都跑一个01背包,看看哪些高度能搭成,最后从高到低枚举检验高度
若某个高度合法输出即可,注意代码实现,有的写法可能爆数组,有的写法可能爆longlong,可惜,我都试过了,血与泪啊。
1 #include<cstdio> 2 #include<iostream> 3 #include<cstring> 4 #include<algorithm> 5 6 using namespace std; 7 8 int maxh,high[110]; 9 unsigned long long dp[110][10005]; 10 int h[110][110]; 11 int cnt[110]; 12 int n; 13 14 int main() 15 { 16 memset(dp,0,sizeof(dp)); 17 scanf("%d",&n); 18 for(int i=1;i<=n;i++) 19 { 20 int x; 21 while(1) 22 { 23 scanf("%d",&x); 24 if(x==-1) break; 25 h[i][++cnt[i]]=x; 26 high[i]+=x; 27 } 28 maxh=max(maxh,high[i]); 29 } 30 for(int i=1;i<=n;i++) 31 { 32 dp[i][0]=1; 33 for(int j=1;j<=cnt[i];j++) 34 for(int v=high[i];v>=h[i][j];v--) 35 if(dp[i][v-h[i][j]]!=0) dp[i][v]=1; 36 } 37 for(int i=maxh;i>=0;i--) 38 for(int j=1;j<=n;j++) 39 { 40 if(dp[j][i]==0) break; 41 else if(j==n) 42 { 43 printf("%d",i); 44 return 0; 45 } 46 } 47 return 0; 48 }