洛谷P1504 积木城堡

题解：背包方案总数问题，就对于每一个城堡，都跑一个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 }