首页 > [NOI1998]免费馅饼
头像 Camouflagetch
发表于 2022-04-28 20:33:47
题目链接 对于输入的每行四个数据,由于题目中说到了“当馅饼在某一秒末恰好到达游戏者所在的格子中,游戏者就收集到了这块馅饼”,所以我们首先将从h到1消耗的时间不是v的整数倍的选项通过continue过滤掉。将那些符合题目条件的数,将其能产生的价值保存到二维数组q中,第一维表示水平位置,第二维表示时间, 展开全文
头像 吃口熊泡饭
发表于 2022-07-15 11:03:56
免费陷阱 题目描述 SERKOI最新推出了一种叫做“免费馅饼”的游戏:游戏在一个舞台上进行。舞台的宽度为W格,天幕的高度为H格,游戏者占一格。开始时游戏者站在舞台的正中央,手里拿着一个托盘。下图为天幕的高度为4格时某一个时刻游戏者接馅饼的情景。 游戏开始后,从舞台天幕顶端的格子中不断出现馅饼并垂直 展开全文
头像 流锡
发表于 2021-10-19 11:20:36
思路:dp 开一个dp[i][j]数组,其中i代表位置,j代表时间 然后在馅饼恰好收集到的时候dp[pos][t]+=val(pos代表馅饼位置,t代表下落到的时间,val代表馅饼价值) 之后我们按时间从后往前枚举位置与操作即可 为什么不从前往后枚举? 因为你一开始的位置你是知道是dp[w/2+1] 展开全文
头像 在刷题的单身狗很开心
发表于 2023-10-10 23:16:32
动态规划问题,用时间和水平方向的编号作为一个二维的状态。那么某个时间下某个水平编号所能够得到的最大的分数就是由上一个时间段的状态通过5种移动方式得到的。那么状态转移方程就出来了。因为没有涉及到的编号不存在所谓的转移,所以一开始将数组初始化成-1,判断如果等于-1的话直接跳过。 对于路径:同样通 展开全文
头像 佰谨
发表于 2022-04-29 10:18:03
#include<iostream> using namespace std; using ll=long long; //没必要考虑馅饼的运动,我们只关心馅饼“何时”到达底部。 //只有在某一秒末正好到达的馅饼,才会计数 //以时间为轴进行动态规划,已知起点,未知终点 //故从后往前递 展开全文
头像 Alonse_wa
发表于 2025-01-16 14:52:14
Description 有一个大小为 的大方格,初始小人在位置 。记小人的位置为 ,每秒小人都能够移动至 的范围内。 给不定数个苹果,对苹果 , 在 时刻出现在, 下落速度为 , 价值为 。 求小人通过最优移动能够获得的最大价值和 打印小人每秒的移动策略 Solution 考虑 展开全文
头像 LXNHB
发表于 2023-12-11 06:31:00
一、思考状态转移方程如何写 1、原问题和子问题: 原问题:一个人可以左右移动去接饼,当游戏结束时,接到的饼的最大价值。 子问题:一个人可以左右移动,当到达某一时刻时,接到的饼的最大价值。 可见子问题的求解方式与原问题相同。 2、使子问题是最优解 显然是比较每一个由相同状态转移来的状态,得到最优解就是 展开全文
头像 usx21145328
发表于 2022-01-31 11:27:51
题意: 一个能向左移动1格或两格,向右能移动1格或两格,也能移动0格的人,在水平宽为W,高度为H的区域内,能接到的馅饼的分值最大为多少。馅饼给出了它掉落的初始时刻、水平位置、掉落速度、分值。 思路: 和数塔类似,把饼落到人高度的时间算出来(人占一格高),然后以时间为横坐标,水平位置为纵坐标,创建一个 展开全文