DP练习

kuangbin 基础DP1(已完成)

2. HDU 1029 (opens new window)

大意：给你$N$个数，求至少出现$(N+1)/2$次的数字，$N$保证是奇数。

方法一 $O(n log n)$:

​ 排序，取中间的值

方法二 $O(n)$:

	val = 0, cnt = 0
	while p = read():
		if cnt == 0:
			val = p
			cnt = 1
		else:
            if p == val:
                cnt++
            else:
                cnt--

4. HDU 1074 (opens new window)

贪心能够获得最小罚时的方案，但不能保证字典序最小，故状压dp即可，注意状压的时候，设状态i由状态j转义而来，那么保证罚时不变的情况下，$j$ ^ $i$越大越好(题目所给数据按字典序排列)

11. POJ 1015 (opens new window)

这题据说是让你求 $\vert a - b \vert$ 最小的情况下， $\vert a + b \vert$ 最大的方案，据说 对于前k个人的 $\vert a - b\vert$ 不满足最优子结构~~(后来想想，应该是不满足无后效性)~~

鉴于 $M<=20$ 我们可以使用以下方案

令$dp[i][j]$ 表示选择第i个人时，差为j的 和最大的方案，同时，用另一结构体数组保存对应方案的路径（路径长度不会超过20）

伪代码如下

if(dp[i][j] != -1){
	for(int k=1;k<=n;k++){ //遍历一遍所有人
		if(path[i][j].is_in_path(k)) continue;
		update(dp[i+1][j + diff[k]], dp[i][j], k);
	}
}

BTW, 这题前前后后花了我两个小时！！

BZOJ做题列表

I too vegetable.

题目链接	类型	完成情况	Update	备注
VIRUS 病毒检测 (opens new window)	暴力字符串dp	AC	2019-08-09
HAOI2011 (opens new window)	带权不重叠区间覆盖	水过 && 已补	2019-08-09	暴力$O(N^2)$过不了？加个伪优先队列，9244ms水过去了(时间上限10s)
棋盘制作 (opens new window)	悬线法	AC	2019-08-11	可以对颜色进行特判，也可以把坐标$(x+y)$为奇数的位置进行翻转后,求同色的矩形大小
逆序对 (opens new window)/配对 (opens new window)	逆序对猜想	AC	2019-08-11	猜想需填入的两数满足某种大小关系(前面的小于等于后面的)，然后证明一下即可 Ps.一份代码, AC两题
木棍分割 (opens new window)	水 二分+DP	理论AC	2019-08-11	水题，懒得做了
上升序列 (opens new window)	水	理论AC	2019-08-11	想了个$O(nlogn)$求递增子序列并记录head数组的假算法，没过。还是老老实实$O(N^2)$吧
三色二叉树 (opens new window)	水 基础树型dp	AC	2019-08-11
时态同步 (opens new window)	水 树上贪心dp	AC	2019-08-11	我怎么老是在做水题？？？
兔子与樱花 (opens new window)	树 贪心	看题解AC	2019-08-12	贪心不过关，该练练了...
叶子的颜色 (opens new window)	树 dp	看题解AC	2019-08-12	一句话题解：父节点涂成颜色A，那么本应涂成A的子节点可以不涂，dp即可
落忆枫音 (opens new window) [题解 (opens new window)]	朱刘算法 dp	看题解AC	2019-08-13	昨天有点惨...
数字计数 (opens new window)	数位dp	Unsolved	2019-08-14	昨天也一样...

其他做题列表

题目链接	类型	完成情况	Update	备注
Print Article (opens new window)	斜率优化dp	AC	2019-08-25	头大
[APIO2010]特别行动队 (opens new window)	斜率优化dp	AC	2019-08-25
摆渡车 (opens new window)	basic dp	Unsolved	2019-08-25
[APIO2014]序列分割 (opens new window)	斜率优化dp	AC	2019-08-27	头大
[APIO2014]序列分割 (opens new window)	斜率优化dp + wqs二分	92 pts	2019-08-27	一个头两个大
[SDOI2016]征途 (opens new window)	斜率优化dp + wqs二分	AC	2019-08-28	做多了就有感觉了
[CEOI2004]锯木厂选址 (opens new window)	斜率优化dp	理论AC	2019-08-28	仔细审题
任务安排 (*) (opens new window)[题解] (opens new window)	斜率优化dp	AC	2019-10-13	dp方程中提前计算之后的代价！
[Jsoi2011]柠檬 (opens new window)		OJBOMB	2019-10-13	哭了
CF311B (opens new window)	斜率优化dp	AC	2019-08-29	看了题解才把转移方程推出来,且本题不能使用wqs二分
CF1096D (opens new window)	基础dp	AC	2019-09-09	一句话题解:dp[i][j]代表前i个字符，不含'hard'的前j位时的最小代价
Computer	树 dp	AC	2019-09-16	换根
Acesrc and Travel (opens new window)	树 dp	Unsolved	2019-09-17	换根
Fish eating fruit (opens new window)	树 dp	Unsolved	2019-09-18	我哭了