高级守护
大佬们给一点历代noip笔试试题网站给萌新吧qwq
萌新需要网站（斜眼笑）awa
萌新只有一点点币（斜眼笑）awa
求！qwq
（注：我是萌新awa）
张睿杰在2020-07-10 19:19:04追加了内容
顺便
期待一下资深后面的段位
祝逸凡，宇昊早日突破
资深天翼
高级天翼
你可以从知识树上找哦~
初级启示者
新手光能
上洛谷www.luogu.cn看看
初级光能
蛤
高级光能
zrj，我还以为你要的那个网站呢，你还是我认识的zrj吗
中级天翼
干嘛？
给你设么？
中级天翼
好啊，给你01背包的讲义吧》》》
一、动态规划
动态规划可以看成一个复杂的递推式，对于递推式而言，有几个特征：
递推项，递推起始项，递推关系，递推终点。
在动态规划中，递推项称为状态；
递推的起始项为边界；
递推终点称为目标；
递推关系为状态转移方程。
注：
动态规划的最优化原理：
子问题的局部最优解导致整个问题的全局最优。
动态规划的无后效性原则
某阶段的状态一旦确定，不会受前后状态影响，当前状态是此前历史的一个完整的总结。
二、01背包
问题模型
给定N个物品，其中第i个物品的体积Vi，价值为Wi。有一容积为M的背包，要求选择一些物品放入背包，在使得物品总体积不超过M的前提下，物品的价值总和最大。
状态：用二维数组表示状态
f[i][j]，将前i件物品放入容量为j的背包能获得最大价值；
边界：注意用循环赋值边界
f[0][j]=0,将前0件物品放入容量为j的背包能获得的最大价值;
目标
f[n][m],将n件物品放入总容量为m的背包能获得的最大价值;
转移方程：分情况讨论
1.j>=Vi
即第i个物品能放入容量为j的背包，此时第i个物品可以选，也可以不选。
2.j<Vi
即第i个物品不能放入容量为j的背包，此时问题转化成前i-1个物品放入容量为j的背包最大价值。
综上：
f[i][j]=f[i-1][j] j<Vi
f[i][j]=max(f[i-1][j],f[i-1][j-v[i]]+w[i]) j>=vi
01背包降维
当题目中给出的数据范围比较大时，我们会发现无法定义那么大的数组，这时候我们考虑降维。
即本来用的二维数组表示状态，现在用一位数组
首先观察上述图片，发现当我们在求第i 行第 j 列的状态 f[i][j]时，我们可以发现它只会用到上一行同一列及其左边的状态，所以我们可以将一个二维数组压缩成一维数组。
注意：
虽然实现了降维，降低了空间复杂度，但是时间复杂度仍然是O(n*m)
采纳谢谢！！！
