题解【洛谷P4995】跳跳！

一看题目名字，下意识地认为DP。

打开题目，发现是一道水的贪心，和DP没一分钱关系~~（毕竟是洛谷最水月赛的T2）~~。

废话不多说。

看完题面，首先想到排序。要将乱序的石头高度变为有序，才能更好地想题。

C++排序代码：sort(a+1,a+1+n);

（STL大法好！）

因为要使耗费的体力值最大，所以距离肯定要最长。

又因为地面高度是0，所以肯定要跳到最高的一块石头上才能耗费最多的体力值。

跳到最高的石头上后，为了耗费更多的体力值，就应该跳到距离这块石头最远的石头上，也就是除地面外最矮的一块石头。

跳到除地面外最矮的石头上后，为了耗费更多的体力值，就应该跳到第二高的石头上。

…………以此类推

注意：虽然n很小，但是石头的高度很高，所以应该用long long类型（比赛时我被坑了……），就有了OIer最爱说的一句话：十年OI一场空，不开long long见祖宗。

（扯多了……）

于是我们就有了下列代码：

#include<bits/stdc++.h>//万能头文件，训练时可以用，但在比赛时不推荐使用，常常出现一些莫名其妙的错误

using namespace std;//标准名字空间

long long n/*石头块数*/,a[]/*每一块石头的高度*/,i,j,k,l,s/*计算体力值*/;

int main(){

    scanf("%lld",&n);//输入石头的块数

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

        scanf("%lld",&a[i]);//输入每个石头的高度

    sort(a+,a++n);//将石头的高度从小到大排序

    s=s+a[n]*a[n];//体力值首先应该加上跳到最高的石头上的体力值

    j=;//小跳蛙将要跳到的石头

    k=n;//小跳蛙当前所在的石头

    while(j<k){//如果当前石头比将要跳到的石头高

        l++;//次数加1

        s=s+(a[k]-a[j])*(a[k]-a[j]);//加上此次跳跃耗费的体力值

        if(l%==)k--;//如果跳了奇数次，j就变成当前所在石头，下一个将要跳到的石头为k-1

        else j++;//否则，k就是当前所在石头，下一个将要跳到的石头为j+1

    }

    printf("%lld\n",s);//输出最大体力值

    return ;

}

那一个while循环是这个代码的关键，一定要弄明白！

巴特西

题解【洛谷P4995】跳跳！

最新文章

热门文章

巴特西

题解 【洛谷P4995】跳跳！

最新文章

热门文章

题解【洛谷P4995】跳跳！