-
Notifications
You must be signed in to change notification settings - Fork 2
/
Copy pathCDOJ-DP.muse
70 lines (43 loc) · 10.4 KB
/
CDOJ-DP.muse
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
*** 成电OJ DP专题题解
2011 UESTC ACM Training for Dynamic Programming 专题地址:http://acm.uestc.edu.cn/contest.php?cid=122
**** CDOJ 1055 The Most Wonderful Competition
题意:有一堆人,两个人之间有一个欢乐值,将这偶数个人两两配对使和谐值最大.
解法:基本的 *集合DP*,一看到N只有16的配对问题就应该想到集合DP.用f[n][t]表示已经配了n个人,t为是否配对过的按位压缩的状态获得的最大欢乐值,转移只要扫描每个人,如果没配对则配上,加上获得的欢乐值.倒推记忆化搜索即可.mfs(n,[1111..]).
**** CDOJ 1477 Cheapest Cost
题意:有一连串温度值,要求进行调整,相邻两天温度差不可以超过常数K,改变温度s代价s**2,相邻两天温度差为D,代价为a*d,求代价最小.
解法: *线性连接型DP*,要用 _单调队列优化_.f[i][j]表示前i天已经调整完毕,第i天温度为j度时的最小花费，朴素转移即枚举f[i-1][t]，如果t与j满足要求则转移。O(n**3)，要优化。因为t与j最大相差正负K（常数），又转移量可以常数时间确定，所以可以用单调队列优化，开两个单调队列（一个对应j－k的范围，一个对应j+k的范围，一个温度和转移量都递增，一个温度递减，转移量递增,因为是由f[i-1][]转移f[i][]，所以具体实现是每次用当前的优先队列更新f[i][j]，完毕后清空队列,递增递减各扫一遍j，把f[i][j]加入两个队列。(其实发现单调性我是是写成斜率优化形式发现所有点都是x坐标相同,只有y坐标不同)
**** CDOJ 1499 Strategic Game
题意：一棵树，在每个点上放一个人他就可以看住这个点连着的所有边，问最少放几个人能看住所有边。
解法： *TreeDP*,题目貌似没有保证树是按照父亲到孩子唯一给定的（也可能是我想多了，实际上不需要），也不知道是不是森林，所以先当作无根树（把无向边给两边节点都存，输入每条边只出现一次），所以递归建树，确定根是谁（有哪几个），然后从根开始DP。f[t][0..1]表示对于t节点,0表示在这个点上放人,看住子树的最小人数,1表示不在这个点放人,看着子树的最小人数,转移就是对于1,则每个子节点的0,1取min求和+1,对于0,每个子节点的1求和.
**** CDOJ 1500 AreYouBusy
题意:题意:给多组东西,每组东西有三种情况:至少选一个,至多选一个随意选,每个东西有价值和代价,给定可用的大家,求价值最大。
解法: *混合分组背包* 意思不大,就是麻烦.对于随意取的部分,把每个物品看成独立的直接做背包,对于至多选一个的,占用一个i,枚举每个物品,都从f［i－1］［j－w［］］更新,另外从f［i－1］［j］更新.比较麻烦的是至少选一个的,有物品的代价是0,所以不能说明代价没增加就是一个没用,但是代价增加了就说明至少用了一个了.我的方法是重新开一个背包，初始－1，（包括f[i][0]),然后循环［后］给当前物品本身大小对应的背包一个值比较（这样可处理有0体积的物品），最后将每个不为值-1的容量的背包（包括0的，因为可能有0体积物品）做为物品对主背包做［选且只选一个的背包］(区别是不从f［i－1］［j］更新).
**** CDOJ 1501 Defense Lines
题意:给定一个序列,可以在任意位置去掉总共0个或1个子串,然后在剩余的部分求一个上升的子串,求上升的子串最大长度.
解法: *线性选择型DP*,用 _平衡树优化_.f[i][0..1]表示使用i作为最长上升子串的最后一位的最大长度,0表示之前没有去掉过子串,1表示之前已经去掉过子串.f[i][0]=f[i-1][0]+1 or 1(如果前面的元素小于i处,或者大于等于i处),f[i][1]=max((f[i-1][1]+1 or 1),max(f[j][0] 如果...)+1).需要优化,一个结构体中p表示i处元素,d表示f[i][0],用一个set保存这种结构体,由于不等式的传递性,我们保证p递增时d是递减的,更新f[i][1]时用lower_bound查找最大的小于shu[i]的位置,用这个位置的d更新.然后要是i处结构体的d大于它的p所在位置的d,那么在set中插入,并且向后检查删除保持set的性质.
注意:一定要各种注意边界和set的二分查找，在没有重复的情况下，upper和lower貌似是相同的，都是定位到这个数（如果有）或者这个数后面那个数，也就是可能是s.end()，要特别判断，要想清楚你想要前面的还是后面的再自己处理++--，处理好end的情况，如果已经--就不用了，否则特判.
**** CDOJ 1502 Food Delivery
题意:给一个数轴,上面有些点等送饭,不满意度为c[i]*到达时间,注意速度是v^-1,也就是时间是距离*v.从某个点出发送,问所有人不满意度和最小是多少.
解法: *双调DP*,有一点转换思想，一开始想让已经走过的点代价最小，但是此时转移时要根据已经用的时间算出来，有后效性，因为每个点的代价增加同步，所以状态改为保存所有点的代价最小值，这样每次转移时只与最后一步怎么走有关（增加时间＊未送到点的单位和） [把转移量合并变形，改变存储意义，使更新只与当前操作有关，消除后效性] f[x][y][0..1]表示左边送完了x,右边送完了y,现在待在左边/右边的所有人的最小的已有不满意度.记忆化搜索,f[x][y][0]=min(f[x+1][y][0]+(t+d[x].b)*v*(d[x+1].p-d[x].p),f[x+1][y][1]+(t+d[x].b)*v*(d[y].p-d[x].p)),即是从同一侧走过来还是从另一侧回头过来的,f[x][y][1]同理.
**** CDOJ 1503 Free Candies
题意:有4个堆,每个里面有最多20种不同颜色的糖,有一个容量5的篮子,每次只能从一个堆最上面取一个放入篮子,篮子有两个同色的则取出来,直到篮子满或者堆空,问最多取到多少对糖.
解法: *可行性记忆化搜索*,f[x][y][z][o]表示四个堆分别取到了某个位置的时候是否可行.显然只要之前篮子没有满过,这个状态确定,拿到的糖数和篮子有的糖都是确定的,与顺序无关.预处理出每个堆取到某个位置的时候已经取出的每种颜色的糖的数量.对于DFS到某个状态,如果篮子还没满,就分别从四个堆顶取,看看能不能有新的同色对,改变篮子里的数量和取出的对数,继续DFS.
**** CDOJ 1504 Mountain Number
题意:问给定闭区间[a,b]中,满足数字先单增后单减的数的个数.
解法:计数问题, *按位DP(线性连接型)* f[i][j][0..1][0..1]表示处理到i位,最后一个数字是j,之前有没有位能确保数字小于上界,正在递增/递减 的数的个数,转移各种麻烦,大概就是如果之前没有数字确保小于上界(即都相等),就只能从f[i-1][j==上界]更新,如果有,可从f[i-1][j]更新,要保证增减性,另外递增的只能从递增的更新,递减的可以从递增和递减的更新保证只有一次转折.注意初始不可能的要=0.注意这种问题,如果同时保证上界和下界不好处理,可以只处理上界,然后f[b]-f[a].另外要预处理出每个长度的数字(如100-999)中满足的个数,来加上(如果a,b位数相差1以上).
**** CDOJ 1505 Print Article
题意:给定一列数,划分成多段,没段代价为数和的平方+M,M是常数,问划分后的最小代价.
解法: *线性选择型DP* , _斜率优化_ .f[i]表示最后划分的一段以i结束的最小代价,f[i]=min(f[j]+(s[i]-s[j])^2+M)化简方程可以发现min中满足g=y-k*x的形式,y,x与j有关,k与i有关且随i单增(2*s[i]),数形结合(固定斜率K,直线从最下面移上来,遇到的第一个点),发现最优的点依次在凸壳上,单调队列队尾维护凸壳(类似graham扫描,如果当前点和最上面两个点不满足左转,则队尾点pop继续)(每次f[i]更新完以后写出x,y,加入),更新f[i]则在队头两个比较,如果队头的点更新不如后面的优则可以pop,直到队头为最优的.
**** CDOJ 1506 Robotruck
题意:一个有固定容量的机器人,要依次送一些不同大小的东西,起点在(0,0),收东西的点和起点之间走曼哈顿距离,问送完最少走多少.
解法: *线性选择型DP* _单调队列优化_ f[i]=min(f[j]+d[j+1]+s[i]-s[j+1]+d[i]),裸单调队列即可.
**** CDOJ 1507 Sum of Digits
题意:给定a,b,求出最小的满足数字和为a,数字平方和为b的数.
解法:这个其实是搜索吧...因为只要存在满足的,重新排列就可以最小了.多次查询。。输入只有两个数的话就是一个子问题。。DP一次即可！，DP范围不取n,m,取最大可能的900，8100。记忆化广搜，因为每一位顺序无关，所以从［小到大扩展，广搜队列中长度和大小都是单调的，所以不用比较取大，先出现的直接就是最小的。其实不是DP。。。木有比较 注释掉的部分是之前写的同长度比较大小。。其实不需要。每一位独立性，即使转折点不同，长度相同，前面的转折点靠后，每一位依次比较，注意！］
**** CDOJ 1508 The Bridges of Kolsberg
题意:两边各有一列点,相同类型的点可以连,受益是两点价值和,连的不可以交叉,问最大受益,同时最小的连边数.
解法: *转化为LCS* f[i][j]表示处理到i,j的最大受益,因为向后扩展,所以可以保证建边不会交叉.转移分别在f[i-1][j],f[i][j-1],f[i-1][j-1]+s(如果同类型)
**** CDOJ 1510 Weights and Measures
题意:每个乌龟有自重和承重,必须承重>=上面和自身的自重和,问最多可以堆多少层.
解法: *贪心DP* 比较神奇,因为是安排不同顺序和用不用某一只得到的情况不同,似乎没法DP.考虑贪心思想,把乌龟按总承重从大到小排序可以证明最终结果的顺序一定是这种,于是只与某一只用不用有关.先如果可以确定一个最终结果的顺序，那么容易想到方程就是到第i个的时候，叠了j层，可以达到的最大承重（转化思想：求最大层数，限制因素是下面每层承重的最小值，于是对于每个层数使承重尽量大可以满足常规的DP形式），类似背包。每次转移只要根据用（如果j-1的值允许用，这种题是以f中的值决定转移，不好理解）还是不用的行为确定继承前面j的还是把前面j的和用了这个的情况。最后最大的不为初始－1的f[n]的n就是答案。注意，由于空间降维，j倒序循环，边界f[1]要在循环完再给
以上题目代码请到我的github自行寻找,uestc+题号.cpp https://github.com/mfs6174/mfs6174-ACM