sosdp 可以做的题目:对子集/超集的 dp,这里对子集相关的部分做一下分析
参考资料
设 \(f[mask][i]\) 表示从低到高考虑到 \(mask\) 的第 \(i\) 位(从 0 开始算),而且这 \(i+1\) 位都是 \(mask\) 的子集并且第 \(i+1\) 位及以上都和 \(mask\) 完全相同时的和
那么只需要对 \(mask\) 的第 \(i\) 位进行分析来转移
- 该位为 0,那么显然这一位只能取 0,也就是说 \(f[mask][i] \leftarrow f[mask][i-1]\)
- 该位为 1,那么这一位可以取 0/1 ,\(f[mask][i] \leftarrow \left\{\begin{matrix} f[mask][i-1]\\ f[mask \oplus 2^i][i-1] \end{matrix}\right.\)
代码如:
for(int mask = 0; mask < (1<<N); ++mask){
dp[mask][-1] = A[mask];
for(int i = 0;i < N; ++i){
if(mask & (1<<i))
dp[mask][i] = dp[mask][i-1] + dp[mask^(1<<i)][i-1];
else
dp[mask][i] = dp[mask][i-1];
}
F[mask] = dp[mask][N-1];
}
滚存一下就得到了常见的写法:
for(int i = 0; i<(1<<N); ++i)
F[i] = A[i];
for(int i = 0;i < N; ++i) for(int mask = 0; mask < (1<<N); ++mask){
if(mask & (1<<i))
F[mask] += F[mask^(1<<i)];
}
时间复杂度 \(O(n2^n)\)
标签:matrix,leftarrow,int,mask,sosdp,理解,子集,一些 From: https://www.cnblogs.com/SkyRainWind/p/17070985.html