Loading... ## 题目 *题目有修改* ### 描述 积木国的王子喜欢用积木垒漂亮的城堡。城堡的每一层是一块积木，并且下面的积木比上面的积木大。 王子决定从每一个垒好的城堡中挪去一些积木，使最终每座城堡都一样高。为了使他的城堡更雄伟，他希望使所有城堡都尽可能的高。 请你帮助王子决定应该移去哪些积木才能获得最佳的效果。 ### 输入 第一行是一个整数N(N<=100)，表示一共有几座城堡。以下N行每行是一系列非负整数，用一个空格分隔，按从下往上的顺序依次给出一座城堡中所有积木的厚度。用-1结束。一座城堡中的积木不超过100块，每块积木的厚度不超过100。 ### 输出 一个整数，表示最后城堡的最大可能的高度。如果找不到合适的方案，则输出0。 ## 题解 这是一道的动态规划题，同时又是一道01背包问题。 显然，最终所有城堡的高度不可能超过初始状态时最矮城堡的高度。我们要做的是得到这个最低高度，枚举每个城堡的积木是否可以组合成从1到这个最低高度的高度：王子要移去积木，我们只需累加积木，让问题变成“一些数（某个城堡中的积木）中某些数（选取的积木）的和能否等于某个数（枚举1~最低高度）”。算出每个城堡中积木可以组合的高度，取所有城堡都可以组合的高度中最大的为最终结果。 在算每个城堡的积木可以组合的高度时，不要忘记了DP的基本写法，循环的层次不能写反了。下面是**错误演示**： ```cpp //DP错误演示 for(int h = 0; h <= high; ++h){ for(int k = s[i]-1; k >= 0 && h >= a[i][k]; --k){ f[h] = f[h]+f[h-a[i][k]]; } if(f[h]) ++vis[h]; } ``` 为了避免对于同一城堡同一高度重复标记，标记每一城堡每一高度。 ## 代码 ```cpp #include <cstdio> #include <cstring> #include <algorithm> int n, a[100][100], s[100], vis[10010], high = 1e9; bool f[10010], v[10010]; int main(){ scanf("%d", &n); for(int i = 0; i < n; ++i){ int hsum = 0; for(int j = 0; ; ++j){ int tmp; scanf("%d", &tmp); if(tmp < 0) break; a[i][j] = tmp; hsum += a[i][j]; ++s[i]; } high = std::min(high, hsum); } for(int i = 0; i < n; ++i){ memset(f, 0, sizeof(f)); memset(v, 0, sizeof(v)); f[0] = 1; for(int k = 0; k < s[i]; ++k){ for(int h = high; h >= a[i][k]; --h){ f[h] = f[h]+f[h-a[i][k]]; if(f[h] && !v[h]){ ++vis[h]; v[h] = 1; } } } } for(int i = high; i > 0; --i){ if(vis[i] == n){ printf("%d\n", i); goto ret; } } printf("0\n"); ret:return 0; } ``` © 允许规范转载 赞赏 如果我的文章对你有用，请随意赞赏 赞赏作者 微信
