zcmimi's blog

categories/算法/动态规划/共3篇文章

avatar
zcmimi
2020-02-29

01背包

每个物品只能使用一次

普通多重背包

将可以用多次的物品拆为多个单次使用的物品

转化为01背包

二进制优化多重背包

但每个物品可以用的次数特别大的时候,如果还是直接拆很有可能会tle

[LG 1776 宝物筛选](https://www.luogu.com.c

avatar
zcmimi
2020-01-26

对于类似f_i=\min_{j=1}^{i-1}f_j+val(i,j)的方程

比如val(i,j)=a_i\times b_j,同时包含了i,j两个变量,

这样没法直接用单调队列

如果把val(i,j)展开能转化成$\frac{y{j1}-y{j2}}{x{j1}-x

avatar
zcmimi
2019-12-01

划分dp

题意

每组输入是两个整数nk(1\le n \le 50, 1 \le k \le n)

输出

对于输入的n,k;

第一行: 将n划分成若干正整数之和的方案数。

第二行: 将n划分成k个正整数之和的方案数。

第三行: 将n划分成最大

1/1
Search
search