两道杂题

（一）

题意

给定\(n\)个区间，\(m\)个关键点，每个区间可以选择选或不选，求将所有关键点覆盖的方案数。

做法

将区间\(l\)升序，\(r\)降序；关键点升序
令\(f_{i,j}\)为前\(i\)个区间已经处理完了，前\(j\)个关键点已经选完了
考虑加入\(i+1:l,r\)
\(\forall k,f_{i,k}\longrightarrow f_{i+1,k}\)
\((k\in[l-1,r))f_{i,l-1\sim r-1}\longrightarrow f_{i+1,r}\)
\((k\in(r,m]),f_{i,k}\longrightarrow f_{i+1,k}\)

（二）

题意

给定长度为\(n\)的01数组B，全\(0\)数组A，及\(m\)个区间，可以将\(A\)数组的区间变成\(1\)，求A,B两数组最少不相同的位置

做法

区间\(l\)升序，\(r\)降序
令\(f_{i,j}\)为前\(i\)个已经考虑过了，\((i,j]\)全\(1\)时，\([1,i]\)的最小贡献
\(f_{i-1,j}\longrightarrow f_{i,j}\)
考虑\((l,r)\)
\((k\in[i-1,r])min\{f_{i-1,k}\}\longrightarrow f_{i,r}\)
\(f_{i-1,i-1}+(b_i=0?-1:1)\longrightarrow f_{i,i}\)

两道杂题

原文：https://www.cnblogs.com/Grice/p/12954629.html