BZOJ 1010 玩具装箱
题意 有n件玩具，玩具长度为ci。连续的玩具可以装进同一容器里，玩具之间要留有1个单位的空间。容器制作费为(X-L)^2，其中X表示容器长度，L表示常量。求最小费用。 数据范围 $$n\leq50000\ \ \ ;\ \ \ L,C_i\leq10^7$$ 题解 动规方程 根据题目描述很容易列出动规方程： 其中 $$s[i]=\sum_{k=1}^{i} c[k]；$$ 而X即为s
标签：DP
BZOJ 1003 物流运输
题意 一批货物从1码头运送到m码头，许n天运完。运输过程中要转停好几个码头。某些天某码头无法转停，此时可以改变运输路线。每次改变路线要花费K代价。从i码头运送到j码头要花费C[i,j]的代价。求运输总代价最小。 数据范围 $$n\leq100\ \ \ ;\ \ \ m\leq20$$ 题解 先预处理出cost[i][j]表示从第i天到第j天航行路线不变时的最小代价，其实就是求最短路。因为n特别小
BZOJ 2748 音量调节
题意 吉他有一个初始音量，吉他手每弹奏一首歌曲，都要将音量改变ci，可加可减，但音量不能小于0，也不能高于max。求最后一首歌曲音量最大值。无解（无法避免音量超出范围）输出-1。 数据范围 $$歌曲数n\leq50\ \ \ ;\ \ \ ci\leq max\ \ \ ;\ \ \ 初始值begin,max\leq1000$$ 题解 数据如此之小……v[i][j]表示第i首歌时音量j是否能达到，
BZOJ 1037 生日聚会
题意 n个男生m个女生排成一排，要求任意一段男生和女生人数差不超过k，求排列方案数。（假设所有男生都一样，所有女生都一样）答案取模。 数据范围 $$n,m\leqslant150\ \ \ ;\ \ \ k\leqslant20$$ 题解 数据这么小，一想就是DP，但没想到是四维的……f[i][j][x][y]表示前i个人中有j个男生，且从后面起男生最多比女生多x个，女生最多比男生多y个。f[i+
BZOJ 1296 粉刷匠
题意 n条木板，每条木板上有m个格子，每个格子有目标颜色0或1。一次可以粉刷连续若干格，每格只能被粉刷一次。T次粉刷后最多有多少格子颜色正确。（初始无颜色） 数据范围 $$n,m\leqslant50\ \ \ ;\ \ \ T\leqslant2500$$ 题解 泛化背包很久以前就讲过，但一直没有练过，今天是第一次。按照泛化背包的理解，每次先DP一行的状态，求出每一行粉刷i次的答案，再DP所有行