首页 > 代码库 > 魔法石之恋
魔法石之恋
【问题描述】
在《Harry Potter and the Sorcerer‘s Stone》中，想得到魔法石，必须要通过许许多多的测试和游戏。现在阿不思·邓布利多认为这些游戏都具有魔法力，魔法师们能够轻松的通过，我们要增加一些只能够通过智力解决的题目，需要真正的聪明人才能够通过。现在由于我们敬爱的Harry Potter同学时间有限,需要你的帮助，请你帮助他来解决这个问题。必须要在伏地魔之前得到魔法石，这样才能够保护魔法界的安全。
游戏的规则如下：
现有一游戏，玩它时将会有方块有顺序的从屏幕顶端掉下至底部，当它碰到障碍物或底部时将停下，同时自己变成障碍物。游戏规则规定，只能从方块下落前决定下落时的横向位置，使这个方块变成障碍物后的高度最低，且如果有几种横向位置使这个方块变成障碍物后的高度最低时，取最左边的横向位置下落。
【输入文件】（stone.in）
（1）第一行有2个整数，方块数n和屏幕宽度w。
（2）2行到n+1行每行1个整数，为第i个方块的边长a。.
【输出文件】（stone.out）
输出文件stone.out仅包含一个整数，即为最后障碍物的最高点高度。
【输入样例】
3 5
2
1
3
【输出样例】
4
【注释】
绿的为方块1，蓝的为方块2，紫的为方块3。
//每次都选择保证最底点且最左
【数据规模】
对于100%的数据
1<=w<=20
1<=a<=w
1<=n<=100
/* 模拟*/#include<cstdio>#include<iostream>#define N 25#define INF 1000000000using namespace std;int high[N],w,n;int main(){ freopen("jh.in","r",stdin); scanf("%d%d",&n,&w); for(int i=1;i<=n;i++) { int a,pos,minn=INF; scanf("%d",&a); for(int j=1;j+a-1<=w;j++) { int maxn=0; for(int k=1;k<=a;k++) maxn=max(maxn,high[k+j-1]); if(maxn<minn) { pos=j; minn=maxn; } } for(int j=1;j<=a;j++) high[j+pos-1]=minn+a; } int ans=0; for(int i=1;i<=n;i++) ans=max(ans,high[i]); printf("%d",ans); return 0;}
魔法石之恋
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。