[结论 + 组合] UOJ144. 【UER #5】万圣节的糖果

神结论题...太菜了根本想不到啊...

有结论可以把奇偶性不同转化为相同:

\(f(i,j,k)\) 表示原题条件情况下,放了 \(1\)\(n\) ,有 \(j\) 个集合末尾奇偶和 \(i\) 相同,\(k\) 个奇偶性不同。

\(dp(i,j,k)\) 表示相同集合奇偶相同的情况,定义同上。显然这个可以 \(O(n^2)\) 求。

有结论 \(f(i,j,k)=dp(i+1,k+1,j)\) ...

Read More

[DP] Codeforces 930C. Teodor is not a liar!

题面意思是在保证不发现问题的情况下询问最多的点。

考虑不发现问题是怎样的情况,应该是个单峰的,所以只要求以最长的单峰子序列即可。

正反刷两趟 \(DP\) ,树状数组优化。

Read More

[DP] BZOJ1566 [NOI2009] 管道取珠

巧妙的 \(DP\)

如果定义 \(f(i,j)\) 表示 上面取了 \(i\) 个,下面取了 \(j\) 个的贡献,发现转移时很难合并贡献...

所以有这样一个精妙的计数方法:

Read More