梨小畅

分类

题解(57)

/ 注册

全部文章（共8篇）

题解 | #[NOIP2011]选择客栈#

思路枚举右端点 i 当 fee[i] <= p 时，对其有贡献的左端点是：i 左侧所有与 i 同色的点当 fee[i] > p 时，对其有贡献的左端点分为两种： (1) i 左侧，所有与 i 同色的，fee[j] <= p 的 j 点显然：位置 j < 位置 i...

思维 dp

2021-08-12

2 530

题解 | #选择客栈#

思路枚举右端点 i 当 fee[i] <= p 时，对其有贡献的左端点是：i 左侧所有与 i 同色的点当 fee[i] > p 时，对其有贡献的左端点分为两种： (1) i 左侧，所有与 i 同色的，fee[j] <= p 的 j 点显然：位置 j < 位置 i...

dp 思维

2021-08-12

2 343

题解 | #Rinne Loves Dynamic Graph#

思路求从 1 到 n 的最短路，需注意的是图上所有边的边权会实时改变如何改变：每次走过一条边之后，所有的 x 都会执行一次操作：x = 1/(1-x)，x 是边权，所有的 x 指所有边即边权会随着走过的边的数目的改变而改变所以该题不再仅仅是最短路问题，而是变成了最短路 + dp 问题...

最短路 dp 思维

2021-07-10

1 362

题解 | #Rinne Loves Graph#

思路求能从 1 号点到达 n 号点并且满足相关条件的最短路条件：穿过的被***城镇不能超过 K 个解法：最短路＋ dp dist[i][j]：从起点开始穿过了j个被***的城市到达i点的最短距离ps：dist 最后一定是最短距离，但中间过程的值不一定是，因为后续可能被再次更新所...

最小生成树 dp

2021-07-09

6 504

题解 | #[NOIP2009]最优贸易#

题意在从 1号点到 n号点的路径中，选择两个城市 A 和 B，必须先选 A 再选 B，问能赚取的差价最大是多少A：买入水晶球B：卖出水晶球 ps：1 号点到 n 号点的路径可能不止一条 . 思路不妨遍历 n 个点，对于每个点求出 res_i = w2[i] - w1[i]w1[i]：买入...

预处理 dp 最短路

2021-07-08

2 431

题解 | #困难的数学题#

c题题解思路状态表示：f[i] => 组成正整数i的方案数（组成i：若干个正整数相加得到的和为i）由题意知：相加序列中的每个数都大于或者等于k 所以可进行集合划分如下： case 1：相加序列中的最后一个数为k.因为减去k之后和为i-k，所以此时的方案数为 f[i-k] case 2...

思维 dp

2021-05-24

6 392

题解 | #值钱的项链#

F题题解思路线性dp (1)状态表示： f[i][0]：长度为i且第i个珠子为蓝色时的最大价值，若第i个珠子不可以为蓝色，则值为负无穷 f[i][1]：长度为i且第i个珠子为红色时的最大价值，若第i个珠子不可以为红色，则值为负无穷 w[i][0]：第i个位置蓝色珠子的最大价值，若无蓝色...

思维 dp

2021-05-24

3 409

题解 | #串#

A题题解思路使用动态规划。我们不妨令 L[i] 来表示长度为i的且含序列"us"的字符串的种类对于L[i]进行集合划分： ① 在第i个字符前“us”已经产生，所以第i个字符可以任意取 => L[i-1]*26 ② 在第i个字符时才产生“us”，此时第i个字符一定是‘s’ =>...

快速幂思维 dp

2021-05-23

3 474