当前位置: 首页 > 编程日记 > 正文

POJ 1038 Bugs Integrated Inc (复杂的状压DP)

\(POJ~1038~~*Bugs~Integrated~Inc:\) (复杂的状压DP)

ZjUKtx.png

ZjU8je.png



\(solution:\)

很纠结的一道题目,写了大半天,就想练练手,结果这手生的。其实根据之前那道炮兵阵地就不应该写的,但是总觉得自己的思路会好一些,码量又小。

博主的核心思路其实就是用一个二进制数来压缩三行的状态,因为二进制的左移右移很方便。然后就是如果三进制会很不好转移。

  1. 我们可以用一个二进制数来预处理压缩出第 \(i\) 往下三行的障碍状态,前 \(m\) 个二进制位表第 \(i\) 行,中间 \(m\) 个二进制位表 \(i+1\) 行,后 \(m\) 个二进制位表第 \(i+2\)

  2. 我们设一个长方体用坐上角那个点表示

  3. 我们可以用搜索来搜出一行内的长方体放置方案,这个很好写,线面代码里唯一一个手写函数就是用来求这个的。它同样用一个二进制来表示出,这个方案里三行被长方体覆盖的状况。

  4. 然后我们需要用步骤3里的单行放置方案来求出上下两行的方案拼接方案(其实就是用一个二进制将两行的方案压缩进来)。直接暴力枚举单行放置方案,再用二进制与运算来判断是否有冲突:如下

  5.      for(rg i=1;i<=tt;++i)for(rg j=1;j<=tt;++j)if(!((b[i]>>m)&b[j])){r[++st]=j; p[i][j]=st; //r表示方案的下面一行用的那个单行方案g[st]=(b[i]>>m)|b[j]; //找出两行的放置方案}
  6. 然后我们设状态就必须将前两行的状态都包含进去:设 \(f[i][j]\) 表示第 \(i\) 行前两行状态为 \(g[j]\) 意义在上面代码里

  7. 然后我们就可以开始常规转移,但是数组 \(r\) 和数组 \(p\) 一定要搞清楚!



\(code:\)

#include<iostream>
#include<cstdio>
#include<iomanip>
#include<algorithm>
#include<cstring>
#include<cstdlib>
#include<ctime>
#include<cmath>
#include<vector>
#include<queue>
#include<map>
#include<set>#define ll long long
#define db double
#define rg register intusing namespace std;int n,m,ff,tt,st,ans;
int a[155];
int b[305];
int c[305];
int g[3005];
int r[3005];
int p[305][305];
int f[155][3005];inline void dfs(int i,int v,int vv){ //用一个二进制表示一行的状态(在某一行放,下面两行都有可能被覆盖,用一个二进制将这三行压在一起)if(i==m){b[++tt]=v; c[tt]=vv; return ;} dfs(i+1,v,vv); //导入方案if(i+3<=m)dfs(i+3,v|(7<<i)|(7<<(i+m)),vv+1); //放入横的长方体if(i+2<=m)dfs(i+2,v|(3<<i)|(3<<(i+m)|(3<<(i+m+m))),vv+1); //放入竖的长方体
}int main(){rg t; cin>>t;while(t--){cin>>n>>m>>ff; ans=0; //读入memset(a,0,sizeof(a));memset(f,0,sizeof(f));tt=0; st=0; dfs(0,0,0); //初始化for(rg i=1;i<=tt;++i)for(rg j=1;j<=tt;++j)if(!((b[i]>>m)&b[j])){r[++st]=j; p[i][j]=st; //r表示方案的下面一行用的那个单行方案g[st]=(b[i]>>m)|b[j]; //找出两行的放置方案}for(rg i=1;i<=ff;++i){rg x,y; cin>>x>>y;a[x]|=1<<(y-1);} a[n+1]=(1<<m)-1; //障碍的二进制读入,最后还要加一行障碍,防止长方体出界for(rg i=1;i<=n;++i){a[i]|=(a[i+1]<<m)|(a[i+2]<<(m+m)); //连续三行障碍压进一个二进制里for(rg j=1;j<=st;++j)for(rg k=1;k<=tt;++k)if(!(((g[j]>>m)|a[i])&b[k])){ //这一行放的方案与前面的方案还有障碍不会冲突f[i][p[r[j]][k]]=max(f[i][p[r[j]][k]],f[i-1][j]+c[k]);ans=max(ans,f[i][p[r[j]][k]]); //因为多加了一行障碍,不用怕出界}} printf("%d\n",ans);}return 0;
}

转载于:https://www.cnblogs.com/812-xiao-wen/p/11210405.html

相关文章:

Blender基础入门学习教程 Learning Blender from Scratch

Blender基础入门学习教程 Learning Blender from Scratch 流派:电子学习| MP4 |视频:h264&#xff0c;1280720 |音频:aac&#xff0c;48000 Hz 语言&#xff1a;英语中英文字幕&#xff08;根据原英文字幕机译更准确&#xff09;|大小:5.5 GB |时长:7h 28m 你会学到什么 云…

android 事件冒泡,Android事件分发

当用户触摸屏幕时&#xff0c;系统会对触摸事件做出相应的相应&#xff0c;这个事件会产生一个MotionEvent&#xff0c;系统根据一定的规则将其传递给View进行处理&#xff0c;这个过程就是事件分发机制了。事件的传递分为两个阶段&#xff0c;即捕获阶段和冒泡阶段。捕获阶段&…

sqlserver trigger

1 --2 -- Create database trigger template 3 --4 USE [EasyJobExTest]5 GO6 7 --判断触发器是否存在,存在则删除8 IF EXISTS(9 select top 1 t.name as trigger_name,a.name as table_name from sys.triggers t,sys.objects a 10 where Lower(a.name)section and t.paren…

jenkins+sonarqube流水线脚本模板

pipeline { //这个任务在哪个主机上运行 //agent any//将这个项目运行在slave上 agent { label node1 }//参数化构建,主要设定git_version变量的值 parameters { string(name: git_version, defaultValue: v1.1, description: 选择你要部署的tag??) }stages { //整个部署的任…

苹果手机在火车站被偷的状况下如何定位找回

苹果手机在火车站被偷的状况下如何定位找回。首先打开“itunes”&#xff0c;选择菜单栏的“文件”-“将文件添加到资料库”选择要做铃声的歌曲&#xff0c;单击“打开”歌曲会出现在“资料库”的“音乐”里右击歌曲&#xff0c;选择“显示简介”选择“选项”填上“起始时间”和…

Blender纹理基础学习视频教程 CGCookie – Fundamentals of Texturing in Blender

Blender纹理基础学习视频教程 CGCookie – Fundamentals of Texturing in Blender Blender纹理基础学习视频教程 CGCookie – Fundamentals of Texturing in Blender Blender纹理基础学习视频教程 CGCookie – Fundamentals of Texturing in Blender CGCookie——Blender纹理基…

14/10/校内测试{天天考,丧心病狂}

1&#xff0c; 给定平面上n个OIer和n台电脑&#xff0c;每个OIer只能水平向右和竖直向下&#xff0c;找到一台电脑写代码&#xff0c;其花费为OIer与电脑之间的曼哈顿距离(|x_i-x_j||y_i-y_j|)。求出使n个OIer均找到自己电脑的最小花费。 输入输出格式 Input/output 输入格式&a…

android 图标拖动不了,拖动式选项卡(仿android) 添加了上下拉刷新后,下拉即刷新,而不是滚动到顶后再刷新,同时还想问一下正在刷新的图标怎么移到选项卡下...

这是我的HTML代码.mui-control-content {background-color: white;min-height: 600px;}.mui-control-content .mui-loading {margin-top: 50px;}新闻音乐sport第一个选项卡子项-1第一个选项卡子项-2第一个选项卡子项-3第一个选项卡子项-4第一个选项卡子项-5第一个选项卡子项-6第…

2022-2028年中国卫星互联网产业深度调研及投资前景预测报告(全卷)

【报告类型】产业研究 【报告价格】4500起 【出版时间】即时更新&#xff08;交付时间约3个工作日&#xff09; 【发布机构】智研瞻产业研究院 【报告格式】PDF版 本报告介绍了中国卫星互联网行业市场行业相关概述、中国卫星互联网行业市场行业运行环境、分析了中国卫星互…

Rhel6-heartbeat配置文档

系统环境: rhel6 x86_64 iptables and selinux disabled 主机: 192.168.122.119 server19.example.com 192.168.122.25 server25.example.com 所需的包:heartbeat-3.0.4-1.el6.x86_64.rpm heartbeat-libs-3.0.4-1.el6.x86_64.rpm heartbeat-devel-3.0.4-1.el6.x86_64.rpm 以下…

Java getBytes字符集问题

今天工作中又一次遇到了java字符集问题&#xff0c;这次是由getBytes方法导致的。 以前的时候&#xff0c;曾经很多次的解决过java字符集以及乱码的问题&#xff0c;以为对这块很了解了&#xff0c;至到今天的又一次深入的学习&#xff0c;才发现以前的认识当中存在的问题&am…

Blender未来科幻武器全流程制作视频教程

Blender 2.9 建模、UV、创建PBR纹理、照明和渲染全面学习视频教程 时长17h 30m 1280X720 MP4 语言&#xff1a;英语中英文字幕&#xff08;根据原英文字幕机译更准确&#xff09; 大小&#xff1a;15.3G 含项目素材 Blender完成PBR艺术创作:科幻板条箱和炮塔 云桥网络 平台hu…

android fragmentpageradapter切换不更新,关于android:在FragmentPagerAdapter中更新当前片段...

我有一个带有标签指示器的viewPager。 ViewPager是带有FragmentPagerAdapter的setAdaper。我对FragmentPagerAdapter的内部工作原理了解甚少。我注意到即使邻居还不可见&#xff0c;邻居片段也会恢复(称为OnResume)。我将更新方法放在OnResume中&#xff0c;以为一旦片段是最新…

高级软件工程的第一次作业:回顾自己本科设计

本科毕业设计&#xff0c;是各位同学大学最后的一个成果&#xff0c;或是一个软件、或是一个游戏&#xff0c;但都体现了大家的辛勤和汗水。 在本课程学习之初&#xff0c;希望大家重拾个人之前的成果&#xff0c;并重新从软件工程的视角&#xff0c;探视设计中存在的不足&…

如何定位并优化慢查询Sql

根据慢日志定位慢查询SQL。 查询慢日志相关变量&#xff0c;并进行设置&#xff1a; 主要关注下述三个变量&#xff1a; long_query_time、show_query_log_file、show_query_log 慢查询sql会被记录到show_query_log_file 日志文件中。 show variables like %quer%; -- 查询…

介绍一个懒人创建springmvc项目的方法(二)

PS: 我是一个懒人,我懒得搭建项目连pom都不想去找,连web.xml都不想配置.所以就会想着找一些简便的办法,来适应我这种懒人. ---------------------------- 本人介绍的是用eclipse和sts插件创建springmvc项目,其他项目目前用不着,等用着的时候在研究吧. 前提: 1 eclipse已经配置好…

python之函数三装饰器

装饰器形成的过程 装饰器的作用&#xff1a;不想修改函数的调用方式&#xff0c;但是还想在原来的函数前后加功能 原则&#xff1a;开发封闭原则 开发&#xff1a;对扩展是开发的 封闭&#xff1a;对修改是封闭的 装饰器的固定模式 计算运行时间 1 import time2 # time.time()获…

Boom Library 93套影视游戏无损配乐音效素材合集包

Boom Library 93套影视游戏无损配乐音效素材合集包 素材压缩包大小共&#xff1a;851G 每个合集为独立压缩包 可选择性下载 云桥网络 平台获取合集包 01.BOOM Library Assault Weapons Bundle【枪战机枪音效】 02.BOOM Library Birds of Prey【猛禽类音效】 03.BOOM Librar…

将数据追加到html 表格中,将数据添加到数据表中

将数据添加到数据表中03/30/2017本文内容在创建 DataTable 并使用列和约束定义其结构之后&#xff0c;您可以将新的数据行添加到表中。 要添加新行&#xff0c;可将一个新变量声明为 DataRow 类型。 当调用方法时&#xff0c;将返回新的 DataRow 对象 NewRow 。 然后&#xff0…

WIN7源码安装Apache和PHP注意事项

安装注意事项。 你注意下下载PHP&#xff0c;Apache的网站&#xff0c;上面有提示要安装Visual C库的。 Apache2.4.4需要VC10库支持&#xff0c;Microsoft Visual C 2010 SP1 Redistributable Package (x64) PHP5.6需要VC11库支持&#xff0c;Visual C Redistributable for Vis…

2022-2028年中国卫星导航行业深度调研及投资前景预测报告

【报告类型】产业研究 【报告价格】4500起 【出版时间】即时更新&#xff08;交付时间约3个工作日&#xff09; 【发布机构】智研瞻产业研究院 【报告格式】PDF版 本报告介绍了中国卫星导航行业市场行业相关概述、中国卫星导航行业市场行业运行环境、分析了中国卫星导航行…

TypeKit ,use online fonts

TypeKit ,use online fonts 相信做UI的同学们经常会碰到字体的取舍问题为了页面的兼容性经常要写像下面的 <style type"text/css">body {font-family: "dejavu sans mono",Arial,Georgia,serif;} </style> 如果想用比较美观的不常见的字体只能…

详解mybatis的insert,update,delete返回值

为什么要提数据的事呢,是因为据说这个save返回的就是插入的数据的条数。但是遗憾的是,我们的这个user怎么能没有id呢,没有id有怎么查,怎么删,怎么改。进来的是没有id的user,出去的是有id的user,真是太厉害了,没想到不仅把返回值改变了,连参数都发生了改变,真是太神奇了。keyProperty=“id” 这是id就是绑定的id,那我就疑惑了,这绑定的哪个id啊。这样一搞,如果插入成功的话返回的是1,如果不成功的话返回的是-1。我让你删id是222222的,我还没创建呢,看你怎么删。

Java--Iterator迭代器(集合的遍历)

在调用Iterator的next方法之前,迭代器的索引位于第一个元素之前,指向第一个元素,当第一次调用迭代器的next方法时,返回第一个元素,然后迭代器的索引会向后移动一位,指向第二个元素,当再次调用next方法时,返回第二个元素,然后迭代器的索引会再向后移动一位,指向第三个元素,依此类推,直到hasNext方法返回false,表示到达了集合的末尾,终止对元素的遍历。

【Stream流】Sort排序详解

很多时候由于需求的复杂性,很多直接从数据库查出的数据并不能直接返回前端,需要进行处理,处理之后又需要排序,这时候一般都会使用Stream流的Sort排序。

使用CruiseControl.Net全面实现持续集成

持续集成想必大家很多人都听说过&#xff0c;甚至都实践过&#xff0c;最近我又一次亲历了一次持续集成&#xff0c;现将我的经验分享给大家。关于持续集成的理论在本文概不涉及&#xff0c;本文的主要目的是实战CruiseControl.Net&#xff0c;用它来全面实现持续集成。 在配置…

Blender三维建模和动画风格化的东方场景视频教程

Blender三维建模和动画风格化的东方场景-Blender 3D Modelling & Animating A Stylized Oriental Scene Blender三维建模和动画风格化的东方场景-Blender 3D Modelling & Animating A Stylized Oriental Scene 时长:23h 40m | .MP4 1280720&#xff0c;30 fps(r) | A…

一条直线上N个线段所覆盖的总长度

转自http://blog.csdn.net/bxyill/article/details/8962832 问题描述&#xff1a; 现有一直线&#xff0c;从原点到无穷大。 这条直线上有N个线段。线段可能相交。 问&#xff0c;N个线段总共覆盖了多长&#xff1f;(重复覆盖的地区只计算一次) 解题思路&#xff1a; 可以将每…

html根据字段制作曲线图,canvas制作简单的HTML图表,折线或者矩形统计(原创)

插件描述&#xff1a;canvas制作简单的HTML图表&#xff0c;折线或者矩形统计 使用canvas制作简单的HTML图表&#xff0c;折线或者矩形统计。使用canvas制作简单的HTML图表&#xff0c;折线或者矩形统计&#xff0c;简单而实用。图形由 Ctable类创建&#xff0c;类我已经写好了…

联合索引最左匹配原则成因

使用col3,col2,col1 顺序建立联合索引&#xff0c;通过col3的值建立一个btree &#xff0c;通过关键值去查找“Alice”&#xff0c;在叶子节点中找到两个“Alice”,那么“Alice”对于col2、col1对应的值&#xff0c;那么会对col2&#xff0c;col1分别进行一个有序的排列&#x…