洛谷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 }

 

上一篇:【ACWing】骑士放置(二分图最大独立集,建图)


下一篇:IDEA java项目,java文件出现橙色时钟,main函数无法执行