HDU-5037 Frog (贪心)

6-17 556 views

传送门

一只青蛙要过河,河里原来有n个石头,河的宽度为m,青蛙一次最多跳l长。在河里加一些石头帮助青蛙过河,同时青蛙想尽可能跳的次数少,你想让它尽可能跳的次数多。问最多跳几次。

思路:参考https://blog.csdn.net/qq_35781950/article/details/75207937

最优策略是跳两次前进l+1长度。

#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <algorithm>
using namespace std;
/*尽可能的让青蛙多跳,。那就是如果那个青蛙
就是在他刚好跳过的第一个地方放石头,给他过

*/
const int maxn=200006;
int st[maxn];
int main()
{   int t;
    int m,n,l;
    scanf("%d",&t);
    for(int tt=1;tt<=t;tt++){
       scanf("%d%d%d",&m,&n,&l);
        for(int i=1;i<=m;i++)
            scanf("%d",&st[i]);
        st[0]=0;st[++m]=n;
        sort(st,st+m+1);
        int k=l;
        int ans=0;
          for(int i=0;i<=m;i++)
          {
            int x=(st[i]-st[i-1])%(l+1);
            int y=(st[i]-st[i-1])/(1+l);
            if(k+x>l)
            {
                ans+=2*y+1;
                k=x;
            }
            else
            {
                ans+=2*y;
                k+=x;
            }
        }
        printf("Case #%d: %d\n",tt,ans);
    }
    return 0;
}
Latest posts by 青鸟千秋 (see all)

CF-1025D Recovering BST(区间dp)

传送门 题意:给定n个整数,问是否能生成一棵BST(二分查找树,左子树都比它小,右子树都比它大),并且有边相连的点权的gcd>1。 思路:区间dp,dp[l][...

阅读全文

牛客网暑期多校第五场E room(费用流)

传送门 题意:有n个宿舍,每个宿舍住4个人,给定去年n个宿舍的人员构成,今年n个4人组合的情况,求最少几个人需要搬寝室。 思路:转化为最小费用最大流解...

阅读全文

HDU-4091 Zombie’s Treasure Chest(暴力)

传送门 题意:有一个容量为n的箱子,和无限多的两种珠宝,体积和价值分别是s1,v1,s2,v2,求能装下的最大价值。 思路:直接暴力枚举会TLE,先计算s1 s2的LC...

阅读全文

欢迎留言