Leven_

DP-----...

2019寒假集训系列(6) 2019春季假集训系列(9) 2019暑期集训系列(12) BZOJ——来自hzwer的千题计划(19) DP------区间DP(5) DP------悬线法(2) DP------树形DP(1) DP------概率期望(2) 【专题系列】(4) 搜索------剪枝(4) 数据结构------分块(1) 数据结构------树剖(2) 数据结构------线段树(8) 数论、数学(5) 未归档(1) 模拟(3) 游记(2) 牛客网(1) 算法------TARJAN(1) 算法------二分答案(1) 算法------并查集(1) 算法------最短路(1) 算法------贪心(2) 算法------高斯消元(3) 题解(2)

/ 注册

全部文章 / DP------线性DP （共5篇）

longpo的回文

啊...比赛的时候输入打错了，结束之后还照着题解把DP部分重构了一遍然而还是WA...样例都没过，然后直接输了-1 明显的DP...而且数据范围这么小，显然怎么搞都可以... 而且这样的回文的DP是很经典的DP啊 f[i][j]表示从i到j所需要最少的价格 $$f[i][j]=\begin{...

2019-04-07

0 401

【LuoguP5004】专心OI - 跳房子

首先这是一道计数类DP，那我们得先推式子，经过瞎掰乱凑，经过认真分析，我们可以得到这样的方程 F(N)=F(0)+F(1)+....+F(N-M-1) 所有F初值为1，F(1)=2 ANS=F(N+M); 那显然我们有这样的代码： 1 #include<iostream>...

2019-02-26

0 440

【DP、线段树优化】琪露诺

跟去年（2017）PJ第四题几乎是一样的？/吐血 DP方程可以很简单的推出来，f[i]=max{f[k]}+a[i] 然而这样做是O(n^2)的看一下数据，200000的话要不nlogn 要不n 由于题解里面单调队列和优先队列都有人用了，那就来一发线段树吧（或者实情是：单调队列不会打？...

DP 线段树

2018-11-04

0 498

poj1958-汉诺四塔问题（三种方法）

链接：http://poj.org/problem?id=1958 大意：汉诺塔升级版，四根柱子，n个盘子，求最少移动次数；两种方法递推or递归（当然还有思路3——打表）思路1：递推（或者DP?) 把四塔转换为三塔进行思考假设当前要移动n个盘子，那么就不如分为以下几步先将上面的...

简单的DP 递归递推

2018-08-20

0 752

【DP】编辑距离

日常吐槽：关于DP，有一种莫名的恐惧...maybe源于与mtw大佬与quantum11大佬，初中时抬老师爬楼梯的经历。。。言归正传：编辑距离【题目描述】设A和B是两个字符串。我们要用最少的字符操作次数，将字符串A转换为字符串B。这里所说的字符操作共有三种： 1、删除一个字符； 2...

简单的DP

2018-08-20

0 430