魔法石之恋

(stone.pas/c/cpp)

【问题描述】

      在《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

【思路】模拟

【code】

#include<iostream>
#include<cstdio>
using namespace std;
#define INF 0x3f3f3f3f
int n,m,h[30],ans,mazz,a,minn,pos;
int main() 
{
    scanf("%d%d",&n,&m);
    for(int i=1; i<=n; i++) {
        scanf("%d",&a);
        minn=INF;
        for(int j=1; j+a-1<=m; j++) {
        mazz=0;
            for(int k=1; k<=a; k++)
                mazz=max(mazz,h[k+j-1]);
            if(mazz<minn)minn=mazz,pos=j;
        }
        for(int i=1;i<=a;i++)h[i+pos-1]=minn+a;
    }
    for(int i=1; i<=n; i++)
        ans=max(ans,h[i]);
    printf("%d\n",ans);
    return 0;
}

RQNOJ魔法石之恋