CF-1238 C.Standard Free2play

题目大意：

有一个墙，高度为h，在每一个高度处都有一个踏板，有的踏板是隐藏着的，有的是伸出来的，小人站在h高度处（题目保证h高度处的踏板一定是伸出来的），这个小人每站到一个踏板上，就可以点一个开关，将他所在的踏板收回，并将下一个高度上的踏板改变状态。小人只能最多落下两层楼，如果从高度为x处落到高度为x-3处那就会摔的稀碎，当然你肯定不想让他摔死是不是，要是不想摔死就充钱！每充一块钱就能指定一个踏板并改变他的状态。现在问你最少充多少钱能不让小人摔死。

做法：贪心，从第一个挡板开始往下跳，如果下面一直没有挡板，那就一直往下跳，直到跳到有挡板的位置，我们先停在他的上一个高度处，所以现在的状态是，小人处于x高度处，x-1高度处有挡板，那么我们讨论x-2高度处有没有挡板：

1.如果x-2高度处有挡板，那么我们在x处按动开关，x和x-1高度处的挡板都收起，小人恰好落在x-2高度处的挡板，此时站在x-2高度处要考虑的问题又和站在x-1高度处要考虑的问题一样了

2.如果x-2高度处没有挡板，那很显然x和x-1处的挡板收起后小人就嗝屁了，所以我们冲一块钱，让x-1高度处的挡板收起来，然后再按动开关的时候x-1高度处的挡板恰好伸出，小人正好落上去，接下来的操作仍然相同。

综上所述，问题的焦点就在于x-1处挡板下面的那个挡板是和它紧挨着还是隔着一些高度。如果紧挨着就跳过这个问题，否则就冲一块钱。是不是很简单啊，老子想秃噜了头皮也没想出来，最后还是看了老外的代码，&#*%^&_*，果然年纪大了不中用了。

#include<iostream>

#include<cstdio>

#define maxn 200010

using namespace std;

int a[maxn],n,h,T;

int main(){

    scanf("%d",&T);

    while(T--){

        int ans=;

        scanf("%d%d",&h,&n);

        for(int i=;i<=n;i++)scanf("%d",&a[i]);

        a[++n]=;

        for(int i=;i<=n;i++){

            if(a[i]-a[i+]>)ans++;

            else i++;

        }

        printf("%d\n",ans);

    }

    return ;

}

巴特西

CF-1238 C.Standard Free2play

最新文章

热门文章