东溪看水

分类

题解(169)

/ 注册

全部文章（共13篇）

牛妹爱数列

题目有一个长度为 n 的序列 a，保证它是一个 01 序列，并执行以下两种操作：单点修改：将位置 x 上的数翻转（0 变 1，1 变 0）；前缀修改：将位置 1~x 上的数翻转（每个数都 0 变 1，1 变 0）。求：使得数列上的所有数都变为 0 的最小翻转次数。解题思路动态规划 ...

动态规划

2020-08-15

0 527

【牛客编程巅峰赛S1第10场】寻宝

题目牛牛得到了一份寻宝图，根据寻宝图的指示，牛牛在一个的网格中，牛牛的位置在，宝藏的位置在。由于寻宝需要按照特定规则，所以牛牛只能往上走或者往右走。藏宝人为了让故意为难牛牛，在地图中设置了一块长方形的陷阱区域，陷阱左下坐标为，右上坐标为，牛牛要是碰到了陷阱可能会有生命危险。牛牛能顺利找...

牛客编程巅峰赛S1 动态规划

2020-08-15

0 716

【每日一题】Mr. Kitayuta, the Treasure Hunter

题目 Shuseki 群岛是 Yutampo 海中 30001 个小岛的群岛。这些岛沿一条线均匀分布，从西到东编号从 0 到 30000。这些岛屿拥有许多宝藏。在 Shuseki 群岛***有颗宝石，而第颗宝石位于岛上。（） Kitayuta 先生刚到达 0 岛。凭借出色的跳跃能力，他将...

每日一题动态规划

2020-08-14

0 701

【每日一题】小A买彩票

题目已知购买一张彩票需要 3 元，而彩票中奖的金额分别为 1、2、3、4 元，并且比较独特的是这个彩票中奖的各种金额都是等可能的。现在小A连续购买了 n 张彩票，求至少能够不亏本的概率是多少。解题思路动态规划：表示购买了张彩票并得到元金额的方法数目。状态转移方程为：。不亏本的数目总...

动态规划每日一题

2020-08-03

0 650

【牛客编程巅峰赛S1第4场】寻找 520

题目又到了一年 5.20！牛牛准备了一个字符串 S，里面全都是由 '5'、'2' 和 '0' 组成，但有的数字被油污染了，看不清，以 '?' 表示。如果把这些被油污染的部分换成 '5'、'2' 和 '0'，在所有可能的字符串中，位置不同的为 "520" 的子序列共有多少个？将答案模 9982443...

动态规划牛客编程巅峰赛S1

2020-07-31

1 575

【每日一题】涂色PAINT

题目有一条长度为的木板，初始时没有涂过任何颜色。给定一个长度为的字符串，由 R、G、B 这 3 种字符组成，分别表示红、绿、蓝这 3 种颜色。每次可以把一段连续的木版涂成一个给定的颜色，后涂的颜色覆盖先涂的颜色。求最少需要涂色多少次？例如，给定字符串：RGBGR。第一次把木版涂成 RR...

动态规划区间dp 每日一题

2020-07-30

0 629

【每日一题】乌龟棋

题目乌龟棋的棋盘是一行 N 个格子，每个格子上一个分数（非负整数）。棋盘第 1 格是唯一的起点，第 N 格是终点，游戏要求玩家控制一个乌龟棋子从起点出发走到终点。乌龟棋中 M 张爬行卡片，分成 4 种不同的类型（M 张卡片中不一定包含所有 4 种类型的卡片），每种类型的卡片上分别标有 1、2、3、...

动态规划每日一题

2020-07-29

0 927

【牛客编程巅峰赛S1第4场】牛妹的野菜

题目给定一个表示番薯洞的地图，每个番薯洞中有一定数量的番薯。已知番薯洞的连接路径，并规定路径是单向且小序号指向大序号，也无环。可以从任意一处开始挖，然后沿着连接往下挖（仅能选择一条路径），当无连接时，结束。设计一种挖番薯的方案，使得可以挖到更多的番薯。输出路径。方法一深度优先搜索（超时）使用...

动态规划 dfs 记忆化牛客编程巅峰赛S1

2020-07-20

1 768

「木」迷雾森林

题目帕秋莉处于地图的左下角，出口在地图右上角，她只能够向上或者向右行走。现在给出森林的地图，保证可以到达出口，请问有多少种不同的方案。答案对2333取模。0 - 空地1 - 树（无法通过）保证出发点和终点都是空地。解题思路使用动态规划思想。地图左下角的坐标为 (m-1,0)，右上角的坐...

动态规划

2020-07-07

0 655

过河卒

题目 A 点有一个过河卒，需要走到目标 B 点。卒行走规则：可以向下、或者向右。同时在棋盘上的 C 点有一个对方的马，该马所在的点和所有跳跃一步可达的点称为对方马的控制点。卒不能通过对方马的控制点。棋盘用坐标表示，A 点 (0,0)、B 点 (n,m)（n<21，m<21），C 点 (x...

动态规划

2020-07-07

0 565