samzhangqingchuan / editorials Goto Github PK

I want to learn dp from qc dalao

求大佬出图topic

今天刚做的PDD笔试：
给定一组棍子长度，可以拼接，不能折断，问能否构成正方形（正方形有四条边，且四条边相等）
例子：
[1,1,1,1]
YES
[1,1,1,1,2,2,4,4]
YES
[1,2,3,2,1]
NO
我觉得是DFS问题，没做出来。谢谢。

dp[i] = max(sum[i] + dp[j] - common_sum(i, j))
= sum[i] + max(dp[j] - common_sum(i,j))

进入一个区间时 -a，离开一个区间时 +a。当走到 i 位置时，所有还没有关闭的区间 j 都会受到一个惩罚。所以在任意时刻，dp 数组维护的是 dp[j] - common_sum(i,j)。当走过最后一个区间时，由于对于任意 j，common_sum(i, j) 等于 0，所以 max(dp) 就是答案。

刚刚笔试完，凉了
n个数里面选k个，使得k个数相与结果最小
n<=40
1<=每个数字<=2^60
麻烦看下是什么思路，谢谢~

来自leetcode，每次比赛你都在前三！羡慕啊！

1. 在给的树上背包pdf文件里第5节算法里， $dp_r=I_{C_r,W_r} * (\mathbf 1 + dp_{s_1}) * (\mathbf 1 + dp_{s_2}) * \dots$，为何 $*$ 的时候要加 $\mathbf 1$，而不是直接 $* dp_{s_1}$
2. 这个泛化物品的解法，状态定义是什么
3. 大佬能把源代码传到github上来吗？我等hdu已经半个月了，还是宕机状态，实在等不下去了

不知道是不是我记错了，印象中去年你的主页上有一个google doc的链接，里面写了诸如做题熟练度大于见题的心得之类的。

我看了那个文档看到挺有收获的，但现在找不到了，希望能在看到、学习。

谢谢楼主🙏