首页 > 其他分享 >对 sosdp 的一些理解

对 sosdp 的一些理解

时间:2023-01-28 17:58:33浏览次数:60  
标签:matrix leftarrow int mask sosdp 理解 子集 一些

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

相关文章

  • 一些库安装
    seleniumwirefromseleniumwireimportwebdriver参考https://crifan.github.io/selenium_summary/website/plugin/selenium_wire.html  fromwebdriver_manager.chr......
  • 开始认真学习一些专业知识了
       在废了(不完全废,但感觉没太认真)一个学期之后的这个仅剩一个月的寒假里,突然想开始认真了。    在收完过年红包之后,发现有经济自由的感觉真的太棒了!说实在,今天......
  • 一种理解 Slice 的模型
    概述Golang中slice极似其他语言中数组,但又有诸多不同,因此容易使初学者产生一些误解,并在使用时不易察觉地掉进各种坑中。本篇小文,首先从Go语言官方博客出发,铺陈官方给......
  • 对于Java平台的理解
    谈谈你对Java平台的理解?“Java是解释执行”,这句话正确吗? Java本身是一种面向对象的语言,最显著的特性有两个方面,一是所谓的“一处编译,处处运行”(Writeonce,runanyw......
  • Tomcat 解决一些基本配置问题。
    解决Tomcat进入manger管理界面需要账号密码问题第一步,打开Tomcat的conf文件夹进入tomcat-users.xml文件在标签里面复制以下内容<rolerolename="admin-gui"/>``<ro......
  • hashmap的一些性能测试
    目录0.前言1.准备工作。1.1模拟哈希冲突1.2java的基准测试。2.测试初始化长度3.模拟一百万个元素put,get的差异。4.模拟无红黑树情况下get效率4.1将random扩大,哈希冲突严......
  • springboot前端传后端集合的一些问题
     前端不能加qs来处理集合对象,后端接收需要加@RequestBody  mybatis用foreach遍历集合对象:<updateid="updateBatch"parameterType="news">updatenew......
  • 理解MySQL的THREAD_ID和PROCESSLIST_ID
    每个线程至少有两个唯一标识符,一个是操作系统线程ID,另一个是MySQL内部线程ID,MySQL内部线程ID在大多数performance_schema表中以thread_id命名。每个前台线程都有一个指定的p......
  • vue配置反向代理解决跨域__Vue.js
    正向代理与反向代理正向代理:在客户端和原始服务器(originserver)之间架设一个代理服务器,为了从原始服务器取得内容,客户端向代理发送一个请求并指定目标(原始服务器),然后......
  • SAP Fiori Belize 主题应用在 SAPGUI 里的一些要点
    ​​SAPFioriBelize主题应用在SAPGUI里的一些要点​​ 为了遵守Fiori设计指南,SAPGUI里的Belize主题需要在某些方面与之前提供的所有SAPGUIforWindows/......