beckyUp

动态规划

--------------作业---------------(4) ACM算法(15) c++(16) codeforces(8) CSP(2) fft(1) java(8) java图像(1) KMP(4) tcp/ip(4) 二分(5) 二分图匹配(1) 分块(1) 分治(2) 前缀和(2) 区间dp(3) 博弈(2) 后缀数组(1) 图论(8) 字典树(1) 字符串(8) 小技巧(9) 并查集(2) 感悟(13) 操作系统(2) 数据库(3) 数据结构(22) 数论(10) 未归档(7) 构造(2) 树形dp(1) 水题(22) 状压dp(2) 脑洞(1) 自然语言处理(2) 计算几何(5) 计算方法(4) 读书笔记(2)

/ 注册

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

数字三角形问题【简单树形dp】

给定一个由n行数字组成的数字三角形，设计一个算法，计算出从三角形的顶至底的一条路径，是的经过该路径经过数字最大经典的树形dp,状态转移方程如下 dp[i][j]=max(dp[i-1][j-1],dp[i-1][j])+a[i][j]; #include <bits/stdc++.h&...

2018-03-27

0 372

51nod 1183 编辑距离问题

2个字符串，把s1转换到s2最少操作，并且把这个操作过程输出。操作包括3种：删除一个字符，增加一个字符，改变一个字符，操作仅对s1执行，使其等于s2. 分析这个题很想最大公共子序列问题对于两个字符串，如果 a[i]=b[j] 则不必进行操作如果a[i]!=b[j] 那么有三种情况，删...

2018-03-26

0 359

ZOJ - 3747 Attack on Titans [有条件限制的经典递推计数好题]

题目大意是有n个士兵的排列，士兵有GRP三种类型，要求至少有m个G士兵连续，至多有k个R士兵连续，问有多少种方案，答案取模1e9+7 题目分析我们看到这个题目，很显然是一个计数的问题，那么如果从简单入手考虑，假设不存在上述条件，就是有n个士兵，每个士兵有三种类型，很显然就是 3...

2018-02-27

0 347

lightoj 1030 - Discovering Gold[期望]

题目大意：起始位置是1，从1走到n，给你一个骰子（6个面），按点数走，收集每一点上的金子，如果你将要走到的位置在n之内，就继续扔，往前走，如果在n之外，就一直扔到合适的位置为止，求到达n点时的期望分析：这个题是一个求期望的题，那么值得注意的是，当扔在n之外的情况是无效的，所以我们在位置 ...

dp

2017-10-16

0 422

codeforces 812b Sagheer, the Hausmeister

题目大意：从左下角开始出发，把每一行的灯都关闭了，最左和最右是楼梯，向上只能通过楼梯，并且每一层都关完才能上一层，上楼和走过房间的时间都是一分钟，问最短时间这道题就是一个线性的DP 考虑从左和从右两种情况就好了一开始的时候看错题目了，把note 看成是限制条件，就做错了另外一个就是需要...

2017-06-21

0 556

An impassioned circulation of affection（codefoces 814c)

题目大意：给你一串字符，修改其中M个为字符C 输出c最长的个数这个题首先按照字符串，进行预处理，在某段内某字符的个数，因此就能知道在该段内修改m个输出的最多字符个数最后记得进行dp 如果修改更少的情况能够有更长的字串，就更新上去 #include <bits/stdc++.h>...

2017-06-13

0 367

浙大校赛- Course Selection System

There are n courses in the course selection system of Marjar University. The i-th course is described by two values: happiness Hi and credit Ci. If a ...

2017-05-10

0 387

连续最大子列和的动态规划写法

连续最大子列和的动态规划写法题目：给定K个整数的序列{ N1, N2, …, NK }，其任意连续子序列可表示为{ Ni, Ni+1, …, Nj }，其中 1 <= i <= j <= K。最大连续子序列是所有连续子序列中元素和最大的一个，例如给定序列{ -2, 1...

2017-03-01

0 639