近两周ACM之DP总结

时间过的真快啊，转眼又过去了两周，仿佛上次歇写博客就在昨天，虽然离考试周就剩两个周多了，但是依然不能松懈。道理是这样 但事实呢，事实就是我的大部分精力还是给到了复习，感觉确实没有刚开始时的那个劲头那么足了，我也想努力调整好自己的心态合理分配好时间一样都不能落下。
这两周还是DP,DP已经学习了三周有余，大头就是大头，除了搜索外别的最多花费老师两周时间来讲，这家伙好，和搜索一样是三周了。大头也是因为它比较难吧然后又特别有用，他能在整个过程中规划出最优解，最重要的就是它的动态转移方程了，只要写出来它，别的，也不是很好办‘，比如背包问题一般有三重循环，怎么循环，每一层的顺序又是什么，这些都得想清楚弄明白他们每一层的意义。这两周接触了好多各种各样的背包问题，除了简单普通的一个背包问题可以用贪心解决，别的贪心都办不了了，只能用DP来找整个的最优

针对背包问题这个类型就讲了一周多，接下来总结一下我课上和课下所学到的：

01背包：对于每个物品都有选和不选两种选择，在不超出背包容量下求装的最大价值。这个问题又可以分为两类，一类是可以分割，这就简单了，可以完完全全的套用贪心思想，直接按性价比排序然后从前开始挨个取直到刚超出容量时便分割使正好装满。若不能分割，就要用dp

完全背包：完全背包问题与01背包问题大致相同，唯一不同的地方就是循环中的顺序，遍历容量时与01背包相反，是从小到大

多重背包：与0-1背包的差别就是对物品按种类划分，每种物品指定件数。物品i的重量weight[i]大于背包承重j时，背包最大价值为dp[i][j] = dp[i-1][j]，物品i的重量weight[i]小于等于背包承重j时，背包最大价值为dp[i][j] = max(dp[i-1][j - k*weight[i]] + k * value[i], dp[i-1][j])     

分组背包： 背包分组和分组的01背包，一般三层循环，顺序很重要这两者的本质区别也就是两层循环反过来，但是意义完全就不一样了，将其分组的话要把for v=v..0这一层循环必须在for 所有的i属于组k之外这样才能保证每一组内的物品最多只有一个会被添加到背包中，若是对每组背包进行01背包，则就把二三层循环颠倒一下

在多重循环中，通常可以通过降维来优化代码降低复杂度，而且循环的顺序也特别重要，就比如01背包和完全背包，01背包循环容量时是从大容量到小容量，完全背包循环时是从小到大；还有分组背包中的两种情况，也是通过循环顺序来区分的

接下来说几个题

POJ 1384 Piggy-Bank(完全背包)

题意是给出存钱罐的最初重量和容量，求小猪装满金币的情况下价值最小是多少

和别的题不大一样这个是求最小价值，容量简单关键是求出最小价值，那么可以想到初始化和dp条件，初始化为无穷大时要注意dp[0][0]必须设置为0（如果求最大价值的话初始化要为-1）

POJ 1837 Balance（dp01背包）

题目大意是一个天平左右两边各有若干个钩子，总共有C个钩子，有G个钩码，求将钩码全部挂到钩子上使天平平衡的方法的总数。

可以把天平看做一个以x轴0点作为平衡点的横轴，臂力=臂长*重量，当两边的臂力相等的时候平衡dp[i][j]，i为砝码数量，j为平衡状态，0为平衡,j<0向左偏，j>0向右偏，且j不能是负数，所以重新设置一个平衡点7500让所有最重的砝码都挂在左边。用dp[i-1][j]=num 表示把前i-1个钩码全部挂上天枰后得到状态j的方法有num次，dp[i][j+l[k]*w[i]表示在dp[i-1][j] 前提下再在第k个钩子上挂上第i个砝码，但是k]*w[i]乘积的数值相等有多种情况，一个位置可能有多个挂钩这时候dp[i][j+l[k]*w[i]]不等于dp[i-1][j]了。

P2577 [ZJOI2004]午餐                   贪心和dp结合

题目大意是n个人每个人有一个打饭时间和吃饭时间，将他们分成两个队伍。每个人打到饭之后就马上去吃饭，求吃饭总时间最短的方案。

这个需要先利用贪心思想,贪心比较好想，吃饭慢的先打饭节约时间， 先按吃饭时间从大到小排序。

然后就是dp了，f[i][j][k]代表前i个人，在1号窗口打饭总时间j，在2号窗口打饭总时间k，但是明显看出这样最后应该会超时，所以需要优化代码去掉一维。

f[i][j]表示前i个人，在1号窗口打饭总时间j，最早吃完饭的时间。接下来分两种情况：将第i个人放在1号窗口：if(j>=s[i].a) f[i][j] = min(f[i][j], max(f[i-1][j-s[i].a], j+s[i].b));f[i-1][j-s[i].a]是i号人打饭+吃饭的时间不足i-1号人吃饭的时间；将第i个人放在2号窗口：f[i][j] = min(f[i][j], max(f[i-1][j], sum[i]-j+s[i].b));   

poj1821 Fence【队列优化线性DP】

题目大意是k个工人粉刷n道墙，每个工人最多刷L[i]面，并且必须刷第S[i]面，每刷一面可以拿到P[i]的报酬。一面墙至多只能被刷一次。

先按照每个工人必须刷的面s排序，保证所有工人可以在上一个工人之后粉刷，dp[i][j]来表示前i个工人粉刷前j面墙最多所得报酬。对于每个工人i，可以刷也可以不刷，对于每个墙j，可以刷也可以不刷，所以dp[i][j] = max(dp[i -1][j], dp[i][j -1])，dp[i][j] 另一种情况是第i个工人从第k+1块刷到第j块。 k+1 <= s[i] <= j, j - k<= l[i],所以方程dp[i,j]=max{dp[i-1,k]+pi*(j-k)}.循环j，k时可以把i看成是常数，然后就可以优化代码，dp[i,j]=pi*j+max{dp[i-1,k]-pi*k}当j增大时，k的取值上界不变，下界增大。如果有两个决策k1,k2满足dp[i-1,k1] - Pi * k1<= dp[i -1, k2] - Pi * k2那就选k2去除k1。当 j 变大时将小于j-l[i]的决策出队,查询最优决策时，队头就是答案，当有一个新的k需要入队时，检查队尾单调性，把不是最优的k出队然后新k入队。

ps1：在看某个题时又学到一招，有的题得到的结果可能很大已经超过了long long，最大的数字为33位，所以可以将两个long long进行拼接，组成一个超过33位的数

没错的话这应该是假期前最后一篇每周博客了吧，我当然还记得那篇五千字总结，写完这个，就要去奔赴下一个总结啦，我会继续认真对待不松懈的