程序员进阶之算法练习（十二）
前言
题目地址在HDU，输入对应的题号即可看到题目，在百度搜索hdu+对应的题号可以看到题解。 我简单的对题目难度进行了划分：
- 简单题：想法题，实现简单，有经验的猿能思考出解；
- 中等题：用到某些竞赛算法（图论、动态规划、数据结构）；
- 难题：觉得难的题；
正文
hdu 5802（简单题）
题目大意
一个人在win10系统上调节声音，每秒只能按一次。 现在有+加号/-减号按钮，加号按钮每按一次音量会+1； 减号按钮按一次，如果上一秒是+号按钮，或者没有按，音量-1；但是如果上一秒也是按减号按钮，这次的减去的音量会是上一次的2倍；（连着按-按钮，音量减少的数值分别是1、2、4、8...） 注意：如果当前音量是7，再减去音量8，会变成0。 问P->Q至少需要多少秒。
题目解析
直接搜索，因为减的次数不会太多。 加上一个贪心的性质：每次尽可能的减，比如说要变小17，那么最好是连着减1、2、4、8 或者1、2、4、8、16，不会是1、2、4。
题目恶心在描述不清楚，训练过程中因为以下的描述导致一直WA。
注意：如果当前音量是7，再减去音量8，会变成0。
hdu 5803（中等题）
题目大意
给出a、b、c、d四个数字，询问 a+c>b+d && a+d≥b+c && 0≤a≤A && 0≤b≤B && 0≤c≤C && 0≤d≤D 满足这些式子的四元数(a,b,c,d)有多少； 0≤A,B,C,D≤1e18
题目解析
dp[len][x][y][mask] len表示当前dp的位数，x表示当前式子1的值，y表示当前式子2的值，mask表示abcd当前是否可以任取 这样直接数位dp即可，需要注意，当枚举到第i位的之后，上一位保留的x、y需要乘以2（因为进位了）
hdu 5855（中等题）
题目大意
�M个商店，N个工厂，每个商店获利的条件是建设了指定的k个工厂。求总获利不小于L，工厂建设的时间最大值最小是多少。
题目解析
二分时间的答案，看哪些工厂能建造。 建图按照最大权闭合图。
hdu 4560（中等题）
题目大意
2013年一开始，一档音乐节目“我是歌手”就惊艳了大家一回。闲话少说，现在，你成为了这档节目的总导演，你的任务很简单，安排每一期节目的内容。 现在有N个歌手，M种歌曲流派（Rock，Pop之类），每个歌手都有自己擅长的流派领域，这些资料都已整理好。你的工作是，安排尽可能多场的演唱比赛。每一场比赛所有歌手都必须上场，为了提高收视率，每个人演唱的歌曲类型不能相同，即便一些歌手要被迫选择一些他们不擅长的。同时，为了展现全面性，在不同的演唱比赛上，每个歌手都会安排不同的歌曲流派。 但是问题是，对于任何一个歌曲流派的歌迷，如果超过K个不擅长的歌手演唱了这种歌曲，他们就会表示不满，比如，发一些宣泄不满的帖子微博，为了表示观点挑起事端等等。你当然不希望这些事情与你的节目有关，在这个前提下，你可以任意安排尽可能多的比赛场次。
Input 输入第一行为T，表示有T组测试数据。 每组数据以四个数字N，M，L, K开始。L表示有L组擅长关系，接下来的L行，每一行有两个数字Ai，Bi，表示歌手Ai擅长Bi类型的歌曲。
- 1 <= T <= 100
- 1 <= N <= M <= 74, 0 <= K <= N
- 0 <= L <= N*M
- 1 <= Ai <= N, 1 <= Bi <= M, 相同关系不会重复出现
Output 对每组数据，先输出为第几组数据，然后输出最多比赛场次
题目解析
建图： 当前二分的场次为mid。 每种流派分为两个点，一个代表是被擅长的歌手演唱(设为i)，一个代表不擅长（i+m）。
点 流量
s->i m
i->i+m k
i->擅长歌手 1
i+m->不擅长歌手 1
歌手->dest midhdu 5800（中等题）
题目大意
给定一个由n个元素组成的序列,和s (n<=1000,s<=1000)
求 ：
f (i，j，k，l，m) 指必定选第i，j号元素，必定不选k，l号元素，选的元素总和为m的子集个数。
题目解析
令dp[i][j][s1][s2]表示前i个物品填了j的体积，有s1个物品选为为必选，s2个物品选为必不选的方案数(0<=s1,s2<=2)，则有转移方程dp[i][j][s1][s2] = dp[i - 1][j][s1][s2] + dp[i - 1][j - a[i]][s1 - 1][s2] + dp[i - 1][j][s1][s2 - 1]，边界条件为dp[0][0][0][0] = 1，时间复杂度O(NS*3^2)。
看的的题解，最后*4是因为必选AB可以调换位置变成BA，同理非必选，所以答案*4。
总结
最近做算法题目占用了很多空暇的时间，导致于没时间去学习工作上需要的新知识以及更新直播和OpenGL ES相关的文章。 突感自己不能很好的分配时间，在一段连续的时间内只能学一样东西，效率很低。 但一切都是为了CCPC-Final。花这么多时间去复习和学习算法，只是为弥补当年的遗憾。人们常说假如再给一次机会，会如何如何。现在机会就在我眼前，我还是希望自己能把握住。不要求多好的成绩，我希望在报名到正式比赛的这段时间内能够尽力学习和训练。
最近两周的更新主要为算法练习，后续更新工作内容。