精神病科黄主任

dp（动态规划）

cf(33) dfs(3) poj(1) 二分(7) 位运算(1) 双端队列(1) 娱乐(1) 并查集(3) 快速幂(1) 思维(1) 拓扑排序(1) 数学(11) 数论(2) 暴力(8) 最短路(1) 未归档(3) 栈(1) 预处理优化(3) 题解(119)

/ 注册

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

一道经典的dp入门题

一道经典的DP题。。。感觉学DP都是从这题开始的。。。 7 3 8 8 1 0 2 7 4 4 4 5 2 6 5 (Figure 1) Figure 1 shows a number triangle. Write a program that calculates the highest s...

2020-05-01

0 624

金明的预算方案 01背包

金明今天很开心，家里购置的新房就要领钥匙了，新房里有一间金明自己专用的很宽敞的房间。更让他高兴的是，妈妈昨天对他说：“你的房间需要购买哪些物品，怎么布置，你说了算，只要不超过N元钱就行”。今天一早，金明就开始做预算了，他把想买的物品分为两类：主件与附件，附件是从属于某个主件的，下表就是一些主件与附件...

2020-05-01

0 580

Rabbit的工作(1)

Rabbit的工作(1) 思路：对于是0的位置直接选择休息，对于是1的位置要么工作，要么休息，二选一的问题，有点像01背包的选或者不选的问题，所以考虑效仿01背包。答案是要求最多共工作了几天，那么开一个维度表示共工作了几天，因为此题跟连续工作的天数有关，所以我们需要加一个维度表示目前为止连续工作的...

2020-05-01

1 755

poj 2479/2593 两个不相交区间的最大子段和 dp

2479 2593 这两题所要求的是一样只是输入不太一样而已思路：其实这题算是求一个序列的最大子段和的一个拓展延伸对于最大子段和我们知道dp[i]=max(dp[i-1]+a[i],a[i]) 表示以i结尾的最大子段和那么这题所要求的是要两个不相交的所以我们考虑开两个数组l,r ...

2020-05-01

0 632