CoolGuang!

动态规划

atcoder(4) kuangbin刷题记录(9) Task In College(1) 二分查找(5) 位运算(2) 博弈论(1) 图论(27) 备忘录(2) 大模拟(7) 字符串算法(3) 思维锻炼(14) 搜索(9) 数据结构(10) 数论(6) 暴力与随机数(3) 未归档(8) 矩阵练习(6) 组合数学(3) 计算几何(1) 计算机知识/辅助工具(1) 贪心算法(4) 路漫漫其修远兮(2) 题解(27)

/ 注册

全部文章 / 动态规划（共10篇）

牛客练习赛60 —— 操作集锦

题意简化一下：给出一个字符串S，求S中有多少个本质不同的长度为k的序列.题解思路：其实刚开始看这题的话，思路是懵的。But：没有思路的时候就看一下数据范围k<=1000,n<=1000这可能是暗示我们要 n*k的方法去写。之后我便直接推了一个dp方程：一、首先：本能反应：二、由...

牛客练习赛60 操作集锦题解

2020-03-27

1 740

最大子段和与最大m子段和&&基础DP1

今天学习了两个基础DP，分享一下。一、最大子段和求一段序列中的一段子序列，使得这段子序列的和最大: ①普通做法: 我们完全可以枚举法来做，即二层for循环，第一层枚举起点，二层枚举长度，用一个sum来记录当前的和。枚举完之后，最大子段和即为sum。时间复杂度 O(N^2) ...

2020-01-13

0 842

中石油组队热身赛问题 K: Transport Ship &&二进制优化多重背包

题目描述 There are N different kinds of transport ships on the port. The i^th kind of ship can carry the weight of V[i] and the number of the ith kind of...

2020-01-13

0 665

数位dp 简单例题整理与总结记忆化搜索模板套路

把数位dp的简单题目做了一下,今天做一个总结与整理其实所谓的数位dp做了几道题后发现就是一个模板类型问题,(指的是记忆化搜索强推状态转移就有点difficult了),我的经验下面几点: 1.首先确定上界与限制,就可以使得我们把当前这个数以下的所有数都进行遍历. 2.在过程中我们确定如何保留...

2020-01-13

0 1099

北大ACM训练赛切割回文划分dp

阿福最近对回文串产生了非常浓厚的兴趣。如果一个字符串从左往右看和从右往左看完全相同的话，那么就认为这个串是一个回文串。例如，“abcaacba”是一个回文串，“abcaaba”则不是一个回文串。阿福现在强迫症发作，看到什么字符串都想要把它变成回文的。阿福可以通过切割字符串，使得切割完之后得到...

2020-01-13

0 677

洛谷动态规划2题 P1006&&P1140

P1006 传纸条题目大意：（简化）一个n*m的矩阵，每一个点对应一个权值。要求你找出两条互不相交的路径从(1,1)出发到右下角(n,m)，问两条路径经过点的最大权值之和。题目思路：这好像是紫书上原题...，不过紫书上是个图看一下这个题，如果把两条路径去掉，就是一个非常简单简单的...

2020-01-13

0 454

Codeforce1225E Rock is Push! 【DP+前缀和】

You are at the top left cell (1,1)(1,1) of an n×mn×m labyrinth. Your goal is to get to the bottom right cell (n,m)(n,m). You can only move right or do...

2020-01-13

0 522

洛谷P1043 数字游戏划分dp入门

丁丁最近沉迷于一个数字游戏之中。这个游戏看似简单，但丁丁在研究了许多天之后却发觉原来在简单的规则下想要赢得这个游戏并不那么容易。游戏是这样的，在你面前有一圈整数（一共nn个），你要按顺序将其分为mm个部分，各部分内的数字相加，相加所得的mm个结果对1010取模后再相乘，最终得到一个数kk。游戏的要求...

2020-01-13

0 519

AtCoder Beginner Contest 145 F - Laminate dp

夜深人静写题解系列？？题意：现在有nn个柱子排在一起，每个柱子有个高度hi,0≤hi≤109hi,0≤hi≤109。现在有至多kk次机会任意修改某些柱子的高度。之后会执行操作：每次可以横向消去一段连续的柱子。问最终最少的操作次数是多少。题解：首先，对于之后执行的操作：对...

2020-01-13

0 548

NOI 2019 多校联合世界树的考验树上差分状压DP

世界树的考验题目大意: 终于，历经千难万险后，路明非来到了世界树下，探寻自己的身世之谜，但世界树却给他出了一道难题。世界树是一个有n（n<=100000）个节点n...

2020-01-13

0 520