AFreeMan

背包型DP

BFS(1) CDQ分治和整体二分(1) Codeforces(15) DFS(4) GDUT训练(8) KMP(1) MST(1) RMQ(2) Trie(1) 二分(3) 几何(2) 区间型DP(5) 单调栈(3) 容斥原理(2) 尺取(1) 差分(1) 广工新生赛题解(1) 序列型DP(1) 思维(1) 拓扑排序(1) 排序(3) 搜索(2) 数位DP(5) 数论(9) 无向图双连通分量(1) 最短路(8) 未归档(95) 杂(5) 栈/(优先)队列/链表(1) 树形DP(2) 树链剖分(2) 棋盘型DP(4) 概率/期望DP(3) 模拟退火(1) 物理(1) 状压型DP(9) 矩阵快速幂(2) 线性DP(4) 线段树/树状数组(8) 组合数学(1) 缩点(不仅SCC)(1) 网络流(4) 莫队算法(2) 贪心(3) 题解(3)

/ 注册

全部文章 / 背包型DP （共4篇）

洛谷P1156 垃圾陷阱

两种状态表示方法。 ①设f(i,j):处理完前i件垃圾，体力值为j的最大高度。先按时间顺序排好序，设a[i].t为第i件垃圾出现时间，a[i].h为第i件垃圾的高度，a[i].f为第i件垃圾所提供体力值。则f[i][j]= max{ ...

2019-01-13

0 452

洛谷 P1541 乌龟棋

https://www.luogu.org/problemnew/show/P1541 2年前做过这道题，不过早就忘了怎么做的了。看到题，先想到用f(p,i,j,k,l)表示当前在位置p，手中有i,j,k,l张四种面值的卡片，已经得到的分数，则f(p,i,j,k,l)=max{f(p-1,...

2018-12-23

0 469

洛谷P1616 疯狂的采药

https://www.luogu.org/problemnew/show/P1616 完全背包，可以用一个常数优化，对于同一个价值的量，仅保存花费最小的那个就行了，因为每种都有无限多个。 #include<bits/stdc++.h> using namespace std; ...

2018-12-17

0 465

洛谷P1064 金明的预算方案

https://www.luogu.org/problemnew/show/P1064 分组背包，由于每组里的情况很少，只有5种，所以就不需要每组内部01背包过一遍了。只需要把主件附件放到一组里，像01背包那样，只是在每组里考虑所有的组合。考虑组合时也是需要考虑一下怎么写可以简化代码的。 #i...

2018-12-17

0 473