HDU-2182-Frog

野性酷女 2021-12-23 11:34 123阅读 0赞

### 链接：https://vjudge.net/problem/HDU-2182 ###

### 题意： ###

有一只青蛙，有n个节点，开始时在1节点，有k次往右跳的机会，每次跳的距离是a-b之间。

每个节点有一个值，到达那个节点则总值加上那个值。

求最大能得到的值

### 思路： ###

dp\[i\]\[j\]表示第i个节点，第j次跳跃得到的值。

dp\[1\]\[0\] = a\[0\]。因为第一个节点不用跳就能得到。

### 代码： ###

#include <iostream>
    #include <memory.h>
    #include <vector>
    #include <map>
    #include <algorithm>
    #include <cstdio>
    #include <math.h>
    #include <queue>
    #include <string>
    #include <stack>
    #include <iterator>
    
    using namespace std;
    
    typedef long long LL;
    
    const int MAXN = 1000 + 10;
    
    int dp[MAXN][MAXN];
    int a[MAXN];
    
    int main()
    {
        int t;
        int n, l, r, k;
        scanf("%d", &t);
        while (t--)
        {
            memset(dp, 0, sizeof(dp));
            scanf("%d%d%d%d", &n, &l, &r, &k);
            for (int i = 1;i <= n;i++)
                scanf("%d", &a[i]);
            dp[1][0] = a[1];
            for (int i = 1;i <= n;i++)
            {
                for (int j = i - r;j <= i - l;j++)
                {
                    if (j < 1)
                        continue;
                    for (int m = 1;m <= k;m++)
                        dp[i][m] = max(dp[i][m], dp[j][m - 1] + a[i]);
                }
            }
            int res = 0;
            for (int i = 1;i <= n;i++)
                for (int j = 1;j <= k;j++)
                    res = max(res, dp[i][j]);
            printf("%d\n", res);
        }
    
        return 0;
    }

转载于:https://www.cnblogs.com/YDDDD/p/10640122.html

发表评论取消回复

表情：

评论列表（有 0 条评论，123人围观）

还没有评论，来说两句吧...

相关阅读

相关 POJ 2182-Lost Cows【树状数组+二分】

有n头奶牛，已知它们的身高为 1~n 且各不相同，但不知道每头奶牛的具体身高。现在这n头奶牛站成一列，已知第i头牛前面有AiAi头牛比它低，求每头奶牛的身高。输入格式

秒速五厘米/ 2023年10月09日 11:55/ 0 赞/ 32 阅读

相关 POJ2182 Lost Cows

POJ2182 Lost Cows ![博客图片][format_png] 题目概述 [POJ2182 Lost Cows][] 题目概述给出一个从 1

傷城~/ 2023年03月06日 05:40/ 0 赞/ 31 阅读

相关 POJ 2182 Lost Cows 【二分查找+树状数组】

题目大意在一个1-n的排列中告诉你第i个数前面有多少比它小还原这个排列分析从后向前确定如果最后一个数a[n]=i

r囧r小猫/ 2022年10月06日 04:54/ 0 赞/ 224 阅读

相关【杭电4004】The Frog's Games

![这里写图片描述][20160726134052116] ![这里写图片描述][20160726134100522] 思路：本题用到了二分的思想。青蛙一次跳跃的范围是0

Love The Way You Lie/ 2022年09月24日 05:20/ 0 赞/ 158 阅读

相关 hdoj 5037 Frog 【万恶的贪心】

题目：[hdoj 5037 Frog][] 题意：一直聪明的青蛙，每次能条 l 的长度，河宽为m，喝中心有一些陆地，它会选择尽量少的次数跳，现在上帝可以任意往喝里面

缺乏、安全感/ 2022年08月12日 08:59/ 0 赞/ 159 阅读

相关 HDU 5514 Frogs（巧妙地容斥）（数论）

题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=5514 题目大意：有n个青蛙和m个石头编号为1-m-1，青蛙每次跳Ni步，问每

╰半夏微凉°/ 2022年07月16日 03:15/ 0 赞/ 192 阅读

相关 HDU-4004-The Frog's Games（二分）

The Frog's Games Problem Description The annual Games in frogs' kingdom started ag

港控/mmm°/ 2022年05月28日 03:38/ 0 赞/ 117 阅读

相关 The Frog's Games

Problem Description：青蛙王国的年度游戏再次开始。最着名的比赛是铁蛙铁人三项。Ironfrog Triathlon的一项测试正在跳跃。这个项目需要青蛙运动

﹏ヽ暗。殇╰゛Y/ 2022年05月28日 02:07/ 0 赞/ 116 阅读

相关 HDU-2182-Frog

链接：https://vjudge.net/problem/HDU-2182 题意：有一只青蛙，有n个节点，开始时在1节点，有k次往右跳的机会，每次跳的距离是a-

野性酷女/ 2021年12月23日 11:34/ 0 赞/ 124 阅读

相关 POJ2182-Lost Cows

[http://poj.org/problem?id=2182][http_poj.org_problem_id_2182] include<stdio.h>

古城微笑少年丶/ 2021年11月26日 13:24/ 0 赞/ 224 阅读