标签:单调队列

【题解】 Bank notes 多重背包单调队列优化 BZOJ – 1531

1. 题目

传送门= ̄ω ̄=

注:这是个权限题。。。不过用博客上的bzoj离线版可以看到题目

2. 题解

单调队列优化多重背包模板题。。。
(我这么弱只做的动模板题了)

朴素的递推式是:$f[......]

[继续阅读= ̄ω ̄=]

Read MoreComment

【算法】多重背包单调队列合集 -boshi

T1.Coins(POJ1742)

多重背包最基本的状态转移方程是这样的: 用f[i][j]表示前i个物品装进背包占容量为j时的最大价值。
$$

题意:

求用n种硬币每种c[i]个最多可以凑出多[......]

[继续阅读= ̄ω ̄=]

Read MoreView 3 Comments

【算法】单调队列优化动态规划—litble

什么是单调队列

单调队列就是元素单调的队列,譬如一个队列中的元素为1,2,3,4,5,6,单调递增,这就是一个单调队列。咱们先看一道单调队列的模板题:poj2823/洛谷P1886
怎么维护单调队列[......]

[继续阅读= ̄ω ̄=]

Read MoreView 1 Comment