VIJOS-P1059 积木城堡
2024-09-08 13:03:58
洛谷 P1504 积木城堡
https://www.luogu.org/problem/P1504
JDOJ 1240: VIJOS-P1059 积木城堡
https://neooj.com/oldoj/problem.php?id=1240
Description
XC的儿子小XC最喜欢玩的游戏用积木垒漂亮的城堡。城堡是用一些立方体的积木垒成的,城堡的每一层是一块积木。小XC是一个比他爸爸XC还聪明的孩子,他发现垒城堡的时候,如果下面的积木比上面的积木不小,那么城堡便不容易倒。所以他在垒城堡的时候总是遵循这样的规则。 小XC想把自己垒的城堡送给幼儿园里漂亮的女孩子们,这样可以增加他的好感度。为了公平起见,他决定把送给每个女孩子一样高的城堡,这样可以避免女孩子们为了获得更漂亮的城堡而引起争执。可是他发现自己在垒城堡的时候并没有预先考虑到这一点。所以他现在要改造城堡。由于他没有多余的积木了,他灵机一动,想出了一个巧妙的改造方案。他决定从每一个城堡中挪去一些积木,使得最终每座城堡都一样高。为了使他的城堡更雄伟,他觉得应该使最后的城堡都尽可能的高。 任务: 请你帮助小XC编一个程序,根据他垒的所有城堡的信息,决定应该移去哪些积木才能获得最佳的效果。
Input
第一行是一个整数N(N< =100),表示一共有几座城堡。以下N行每行是一系列非负整数,用一个空格分隔,按从下往上的顺序依次给出一座城堡中所有积木的棱长。用-1结束。一座城堡中的积木不超过100块,每块积木的棱长不超过100。
Output
一个整数,表示最后城堡的最大可能的高度。如果找不到合适的方案,则输出0。
Sample Input
2 2 1 -1 3 2 1 -1
Sample Output
3
这道题一开始只想暴力。
但是正在刷背包的题,刷到了这道。
所以这道题的正解应该是背包。
当时蒙圈。
状态是啥啊???
这咋能是背包呢???
然后大佬就告诉我,这道题不能往一般的背包想,得想那些清奇的思路。
其实背包问题千变万化,这道题只是01背包,但是要知道,01背包是背包的基础,是最重要的背包,所有的背包问题,中心思路都是转化成01背包求解。
那么我们开始思考这道带思维的背包。
搭积木完成之后再拿走,就相当于在搭的时候就直接拿走了。所以这道题就转换成01背包:在搭的时候,放还是不放。
跑01背包,dp数组表示的意义是能否达到i高度,如果能,ans[i]数组++,不能就不加。
这样的话从大到小统计最大的符合要求的ans下标就可以了。
代码:
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
int n,sum,tot,maxn;
int ans[],dp[];
int a[];
int main()
{
scanf("%d",&n);
for(int i=;i<=n;i++)
{
memset(dp,,sizeof(dp));
tot=,sum=;
int h;
while()
{
scanf("%d",&h);
if(h<)
break;
a[++tot]=h;
sum+=h;
}
dp[]=;
a[]=h;
maxn=max(maxn,sum);
for(int k=;k<=tot;k++)
for(int j=sum;j>=a[k];j--)
if(dp[j]== && dp[j-a[k]]==)
dp[j]=,ans[j]++;
}
for(int i=maxn;i>=;i--)
if(ans[i]==n)
{
printf("%d",i);
return ;
}
printf("");
return ;
}
欢迎大家在评论区提出疑问或指正。
最新文章
- Python学习总结 03 Plotly 学习总结
- Ruby FFI 入门教程
- int main(int argc, char * argv[]) 里的异常处理
- Go语言实现HashSet
- [JAVA设计模式]第三部分:结构模式
- css伪类选择器详细解析及案例使用-----伪类选择器(1)
- Linux怎样修改系统时间
- Sublime Text3中最常用的快捷键
- Java 练习(多态,instanceof)
- MyBatis开发中解决返回字段不全的问题
- MySQL ID排序乱了的解决办法
- mysql 关联表修改数据
- 利用Python计算π的值,并显示进度条
- eletron打包
- layui(九)——flow组件常见用法总结
- node 下less无法编译的问题
- Dubbo源码解析之registry注册中心
- 【java编程】格式化字符串
- Java基础学习笔记(三)
- Spring Security教程(五):自定义过滤器从数据库从获取资源信息
热门文章
- Fink| CEP
- 实现ElementUI Dialog宽度响应式变化
- RestTemplate的三种请求方式
- A query was run and no Result Maps were found for the Mapped Statement
- .NET Core 学习笔记之 WebSocketsSample
- 『The Counting Problem 数位dp』
- kali渗透综合靶机(七)--Super-Mario-Host靶机
- VMware+windbg时快照功能的使用
- yield return,yield break
- 算法笔记 第6章 C++标准模版库(STL)介绍 学习笔记