Feng003

分类

codeforces(2) DP(3) 图论(2) 基础数据结构(2) 字符串(1) 数据结构课程(1) 概率期望(1) 算法课课程作业(4) 题解(6)

/ 注册

全部文章（共4篇）

DP入门

动态规划算法（DP,Dynamic Programming）它针对满足特定条件的一类问题，对各状态维度进行分阶段、有顺序、无重复、决策性的遍历求解。阶段动态规划算法把原问题视作若干个重叠子问题的逐层递进，每个子问题的求解过程都构成一个阶段。在完成前一个阶段的计算后，动态规划才会执行下一阶段的计...

DP

2021-01-26

0 744

破忒头的匿名信(AC自动机套dp)

题意：给你n个字符串，每个字符串s[i]都有相应的花费代价cost[i]。问用这些已有的串拼出一个给定的T串的最小花费是多少。思路：已知有n个模式串，再给出一个匹配串。很标准的一道AC自动机的题，花费最小的话也很容易想到用dp来做，dp[i]代表能拼出T[1~i]的最小花费,转移方程 dp[i]=...

DP AC自动机

2020-07-07

0 616

最大连续乘积子数组

给定一个长度为N的浮点数数组a。请找出其中乘积最大的子数组。例如，给定数组{-2.5, 4, 0, 3, 0.5, 8, -1}，则取出的最大乘积子数组为{3, 0.5, 8}。也就是说，在上述数组中，3 , 0.5和8这三个数是连续的，而且乘积是最大的。思路：设计状态代表以结尾的子数组中，乘积...

DP

2020-05-22

0 583

Array Without Local Maximums（codeforces1068D）计数类DP

题意：给你一个长度为n的数组a,（1<=n<=1e5 ,1<=a[i]<=200 or a[i]=-1）。a[i]=-1代表i这个位置的数是未知的否则已知，对于每个未知的数你可以把它设置成1-200之间的任意整数。问你有几种设置方法可以使得整个序列满足：a[1]<=a[...

计数类dp DP

2020-04-19

0 566