[GN] DP学习笔记板子
文章目录
- Bitset
- 滚动数组
- 多重背包
- 区间DP
- 树形dp
- 状压dp
- 模拟退火
Bitset
使用bitset需要引用<bitset>头文件。
其声明方法为:
std::bitset<N>s; (N为s长度)
常用函数:
b.any() 判断b中是否存在值为1的二进制位
b.none() 判断b中是否不存在值为1的二进制位
b.count() 判断b中值为1的二进制位个数
b.size() 判断b中二进制位的个数
b[pos] 访问b中在pos处的二进制位
b.test(pos) 判断b中在pos处的二进制位是否为1
b.set() 把b中所有二进制位都置为1
b.set(pos) 把b[pos]置为1
b.reset() 把b中所有二进制位都置为0
b.reset(pos) 把b[pos]置为0
b.flip() 把b中所有二进制位逐位取反
b.flip(pos) 把b[pos]取反
滚动数组
memset(dp, inf, sizeof(dp)) ;dp[0][N]=0;for(int k = 1, i = 1; i <= n; i ++, k ^= 1){memset(dp[k], inf, sizeof(dp[k])) ;for(int j = -5000; j <= 5000; j ++)dp[k][j + N] = min(dp[k ^ 1][j + c[i] + N], dp[k ^ 1][j - c[i] + N] + 1) ;}int ans;for(int i=0;i<=5000;i++){ans=min(dp[n&1][i+N],dp[n&1][-i+N]);if(ans<1000) break;}
多重背包
//分堆过程while(k<=s){//小于等于和小于都可以,因为如果出现等于的情况就是s=2^(k+1)-1,下面的if判断会处理掉cnt++;//cnt先++=>下标从1开始w[cnt] = k * wi;//k个物品为一堆v[cnt] = k * vi;s-=k;k*=2;}if(s>0){//如果存在最后一个堆cnt ++;//最后一个堆有s'个i物品w[cnt] = s * wi;v[cnt] = s * vi;}}n = cnt;//物品由n个变成了nlogs个 别忘了这句
区间DP
for (int len = 1; len <= n; len++) { // 区间长度for (int i = 1; i + len - 1 <= n; i++) { // 枚举起点int j = i + len - 1; // 区间终点if (len == 1) {dp[i][j] = 初始值continue;}for (int k = i; k < j; k++) { // 枚举分割点,构造状态转移方程dp[i][j] = min(dp[i][j], dp[i][k] + dp[k + 1][j] + w[i][j]);}}}
树形dp
void dfs(int u,int fa){for(int i=0;i<g[u].size();i++){int v = g[u][i];if(v==fa) continue;dfs(v,u);for(int k=m;k>=0;k--)for(int j=1;j<=k;j++)dp[u][k] = max(dp[u][k],dp[u][k-j]+dp[v][j]);}for(int i=m;i>=1;i--){dp[u][i] = dp[u][i-1] + w[u];}}
状压dp
f[0] = 0;
for (int mask = 1; mask < (1 << n); ++mask) {for (int i = 0; i < n; ++i) {if (mask & (1 << i)) {f[mask] = min(f[mask], f[mask ^ (1 << i)] + (nums1[__builtin_popcount(mask) - 1] ^ nums2[i]));}}
}return f[(1 << n) - 1];int f[17][1<<17];
int dfs(int x,int y){if(f[x][y])return f[x][y];int ans=0;for(auto i:v[st[x][st[x].size()-1]])if(!((y>>(i-1))&1))ans=max(ans,dfs(i,y|(1<<(i-1))));return f[x][y]=ans+st[x].size();
}for(int i=1;i<=n;i++)cin>>st[i],v[st[i][0]].push_back(i);for(int i=1;i<=n;i++)ans=max(ans,dfs(i,(1<<(i-1))));1.是方格图求状态数、最大最小值。这种题一般是把每一行/列看做一个状态来转移的。预处理出每一行的所有状态,然后根据状态转移方程进行转移。该状态左右不相邻: !(i& i<< 1) 2.给你一个集合,然后每次从中选出一个数,选过的数不能再选dp[st] += dp[st^(1<<(i-1))] (st&(1<<(i-1)) != 0)
模拟退火
const double eps=1e-18;
const double delta=0.999;//调了一年的参数一般为0.97~1.0class Solution {
public:vector<int> a,b;int ans=INT_MAX;//答案double fun(){int res=0;for(int i=0;i<a.size();i++)res+=(a[i]^b[i]);ans=min(ans,res); //取最小return res;}int sa(){random_shuffle(b.begin(), b.end()); //打乱,随机分布int n=a.size();for(double t=1e6;t>eps;t*=delta){int x=rand()%n,y=rand()%n;int last=fun(); //没有交换前的异或值之和swap(b[x],b[y]); //交换后的异或值之和int now=fun();int de=now-last;if(de<0){ //比当前优秀就要}else if(!(exp(-1.0*de/t)*RAND_MAX>rand())) // 模拟退火的法则,我也搞不懂,背一下就好了swap(b[x],b[y]); //不符合法则,回溯。}return ans;}int minimumXORSum(vector<int>& nums1, vector<int>& nums2) {for(int i:nums1) a.push_back(i);for(int i:nums2) b.push_back(i);return sa();}
};
相关文章:
[GN] DP学习笔记板子
文章目录 Bitset滚动数组多重背包区间DP树形dp状压dp模拟退火 Bitset 使用bitset需要引用<bitset>头文件。 其声明方法为: std::bitset<N>s; (N为s长度)常用函数: b.any() 判断b中是否存在值为1的二进制位 b.none() 判断b中是否不存在值为1的二…...
GLog开源库使用
Glog地址:https://github.com/google/glog 官方文档:http://google-glog.googlecode.com/svn/trunk/doc/glog.html 1.利用CMake进行编译,生成VS解决方案 (1)在glog-master文件夹内新建一个build文件夹,用…...
微信小程序如何实现点击上传图片功能
如下所示,实际需求中常常存在需要点击上传图片的功能,上传前显示边框表面图片显示大小,上传后将图形缩放到边框大小。 实现如下: .wxml <view class="{{img_src==?blank-area:}}" style="width:100%;height:40%;display:flex;align-items: center;jus…...
Windows Qt C++ VTK 绘制三维曲线
Qt 自带数据可视化从文档上看,只能实现三维曲面。 QwtPlot3D在Qt6.6.0上没编译通过。 QCustomPlot 只能搞二维。 VTK~搞起。抄官网demo。 后续需求: 1、对数轴 2、Y轴逆序 3、Z轴值给色带,类似等高线图的色带 期待各位大佬多多指导。…...
Android T 远程动画显示流程(更新中)
序 本地动画和远程动画区别是什么? 本地动画:自给自足。对自身SurfaceControl矢量动画进行控制。 远程动画:拿来吧你!一个app A对另一个app B通过binder跨进程通信,控制app B的SurfaceControl矢量动画。 无论是本地动画还是远程…...
【计算机网络】【练习题及解答】【新加坡南洋理工大学】【Computer Control Network】
说明: 仅供学习使用。 一、题目描述 题目共4问,描述网络通信中的 帧传输时延(Frame Delay)、传播时延(Propagation Delay),以及 链接利用率(Link Utilization) 的相关…...
云计算HCIE备考经验分享
大家好,我是来自深圳信息职业技术学院22级鲲鹏3-1班的刘同学,在2023年9月19日成功通过了华为云计算HCIE认证,并且取得了A的成绩。下面把我的考证经验分享给大家。 转专业进鲲鹏班考HCIE 大一上学期的时候,在上Linux课程的时候&…...
Threejs API——`OrbitControls`相机控件
文章目录 API用法API OrbitControls 相机控制用法 导入import {OrbitControls } from three/examples/jsm/controls/OrbitControls.js import {DRACOLoader,AmbientLight,Color,MOUSE,...
远程教育:低代码在教育技术领域的重塑之力
新冠肺炎大流行对世界各地的行业产生了影响,其中一些行业的影响远远超过其他行业。食品、零售、供应链、娱乐和航空业是受影响最大的行业,为确保不间断运营,这引发了一场数字革命。相信,这种数字化的采用将长期保持下去࿰…...
vue 模板语法值class操作
class.html <!DOCTYPE html> <html lang"en"> <head><meta charset"UTF-8"><title>class</title><!-- 确保引入正确的Vue版本库,下面只是示例,需要替换为实际可工作的CDN地址 --><sc…...
MySQL的原生API实现插入数据后在可视化工具上不显示的问题解决
显示表中有两行数据,该表也设置了主键和唯一索引 点进表里看却没有数据 问题原因出现在这里,虽然很多常用的数据库连接池都会开启自动提交,但ibatis的SqlSession使用sessionFactory.openSession()创建时,默认的自动提交是false&am…...
Blender教程(基础)-内插面、分离、环切、倒角-08
一、内插面 菜单位置如下图位置。 单击需要处理的面,出现一个黄色的圈。 1、菜单选中内插 鼠标悬停在黄色圈内单击左键可以来回实现内插,但是发现并不好操作。 2、快捷键内插 在选中需要操作的面之后,鼠标移动到外面,键盘在英…...
Unity 自动轮播、滑动轮播
如图所示,可设置轮播间隔,可左右滑动进行轮播 1.在UGUI创建个Image,添加自动水平组件 2.添加并配置脚本 3.代码如下,都有注释 using UnityEngine; using UnityEngine.UI;public class IndicatorManager : MonoBehaviour {public …...
纯html+js+css个人博客
首页 <!DOCTYPE html> <html><head><meta http-equiv"Content-Type" content"text/html; charsetutf-8"><title>主页</title><!-- 引入layui css文件 --><link rel"stylesheet" href"layui-…...
二百二十一、HiveSQL报错:return code 2 from org.apache.hadoop.hive.ql.exec.mr.MapRedTask
一、目的 在运行HiveSQL时,执行报错 tatement: FAILED: Execution Error, return code 2 from org.apache.hadoop.hive.ql.exec.mr.MapRedTask 二、在yarn上查看任务报错 The required MAP capability is more than the supported max container capability in t…...
JavaEE学习笔记 2024-1-25 --VUE的入门使用
上一篇 个人整理非商业用途,欢迎探讨与指正!! 文章目录 14.VUE基础14.1VUE的入门使用14.2条件判断14.3循环渲染14.4v-bind绑定标签属性14.5v-model表单标签的双向绑定14.6事件处理14.7axios 14.VUE基础 前端框架 UI框架:页面渲染Bootstrap,L…...
php-fpm详细讲解
PHP-FPM(FastCGI Process Manager)是PHP的一种运行模式,用于处理动态HTTP请求。 它与传统的模块式PHP(如Apache模块)相比,将PHP解析和执行过程单独封装为一个独立的进程池,通过FastCGI协议与We…...
小白水平理解面试经典题目LeetCode 455 Assign Cookies【Java实现】
455 分配cookies 小白渣翻译: 假设你是一位很棒的父母,想给你的孩子一些饼干。但是,你最多应该给每个孩子一块饼干。 每个孩子 i 都有一个贪婪因子 g[i] ,这是孩子满意的 cookie 的最小大小;每个 cookie j 都有一个…...
uniapp 问题汇总-问题数(2)
ios scroll-view无法滚动 使用uview折叠面板嵌套scroll-view 嵌套之后安卓可以滚动,ios无法滚动 <u-collapse accordion opencollapseOpen changecollapseChange ref"uCollapse" :valueuCollapseValue><u-collapse-item :nameindex :title&quo…...
[AG32VF407]国产MCU+FPGA Verilog编写控制2路gpio输出不同频率方波实验
视频讲解 [AG32VF407]国产MCUFPGA Verilog编写控制2路gpio输出不同频率方波实验 实验过程 根据原理图,选择两个pin脚作为输出 修改VE文件,clk选择PIN_OSC,使用内部晶振8Mhz,gpio使用PIN_51和52,pinout是数组 添加pll…...
OpenTK 3.3.3实现3D旋转立方体:C# OpenGL入门实战
1. 为什么一个旋转立方体是3D图形编程真正的“Hello World” 很多人第一次接触OpenGL或现代图形API时,总想直接上手做粒子系统、PBR渲染或者实时阴影——结果卡在顶点缓冲对象(VBO)绑定失败、着色器编译报错、甚至窗口根本没显示出来。我带过…...
Windows HEIC缩略图解决方案:让iPhone照片在资源管理器中重获新生
Windows HEIC缩略图解决方案:让iPhone照片在资源管理器中重获新生 【免费下载链接】windows-heic-thumbnails Enable Windows Explorer to display thumbnails for HEIC/HEIF files 项目地址: https://gitcode.com/gh_mirrors/wi/windows-heic-thumbnails 想…...
Pearcleaner:macOS深度清理终极指南,让磁盘空间翻倍
Pearcleaner:macOS深度清理终极指南,让磁盘空间翻倍 【免费下载链接】Pearcleaner A free, source-available and fair-code licensed mac app cleaner 项目地址: https://gitcode.com/gh_mirrors/pe/Pearcleaner 你是否曾经卸载了macOS应用&…...
【独家首发】DeepSeek边缘计算白皮书未公开章节:3类典型场景QoS SLA保障公式(含实测RTT抖动衰减模型)
更多请点击: https://intelliparadigm.com 第一章:DeepSeek边缘计算架构全景概览 DeepSeek边缘计算架构以“轻量、协同、自治”为核心设计理念,面向AI推理密集型场景构建端—边—云三级协同的分布式智能执行体。该架构并非传统云中心化模型的…...
DS4Windows终极指南:5分钟让PS手柄在Windows电脑上完美运行
DS4Windows终极指南:5分钟让PS手柄在Windows电脑上完美运行 【免费下载链接】DS4Windows Like those other ds4tools, but sexier 项目地址: https://gitcode.com/gh_mirrors/ds/DS4Windows 还在为PS4/PS5手柄在Windows电脑上无法识别而烦恼吗?DS…...
Mapbox Studio Classic快速上手:10分钟创建你的第一个地图项目
Mapbox Studio Classic快速上手:10分钟创建你的第一个地图项目 【免费下载链接】mapbox-studio-classic 项目地址: https://gitcode.com/gh_mirrors/ma/mapbox-studio-classic Mapbox Studio Classic是一款强大的地图设计工具,通过直观的界面和简…...
LVGL事件处理实战:从按钮点击到复杂手势,手把手教你写响应式UI回调
LVGL事件处理实战:从按钮点击到复杂手势,手把手教你写响应式UI回调 在嵌入式系统开发中,用户界面的交互体验往往决定了产品的成败。LVGL作为轻量级通用图形库,其事件处理机制是构建动态交互的核心。不同于简单的回调函数绑定&…...
Seraphine:英雄联盟玩家的5大核心功能终极助手,一键提升游戏体验
Seraphine:英雄联盟玩家的5大核心功能终极助手,一键提升游戏体验 【免费下载链接】Seraphine 英雄联盟战绩查询工具 项目地址: https://gitcode.com/gh_mirrors/se/Seraphine Seraphine是一款专为《英雄联盟》玩家设计的智能游戏辅助工具…...
大语言模型在嵌入式系统开发中的应用与挑战
1. 嵌入式系统开发与大语言模型的碰撞 在智能家居、工业自动化和物联网设备蓬勃发展的今天,嵌入式系统作为连接数字世界与物理世界的桥梁,其开发复杂度正呈指数级增长。传统嵌入式开发要求工程师同时具备三大核心能力:理解电子元件特性与电路…...
Windows用户必看!终极免费的PDF处理工具Poppler快速安装指南
Windows用户必看!终极免费的PDF处理工具Poppler快速安装指南 【免费下载链接】poppler-windows Download Poppler binaries packaged for Windows with dependencies 项目地址: https://gitcode.com/gh_mirrors/po/poppler-windows 还在为Windows系统上处理P…...
