
简单瞎搞题(状压dp bitset)
发布日期:2021-05-10 04:58:32
浏览次数:4
分类:技术文章
本文共 1013 字,大约阅读时间需要 3 分钟。
题目地址:https://ac.nowcoder.com/acm/problem/17193
闲话:这个题目是一个状压dp,不过我的dp一向很垃圾,状压也没怎么练过,做的时候属实看不出来,看了别人的题解才会做。不过我现在也有了一些思考:当只有存在或不存在两种状态时我就可以联想到状态压缩了。 对于这个题目其实到现在也不是特别懂了,还是有些不太明白的先记录下来。题解
这个题目中最重要的就是bitset的运用。首先我们需要知道bitset是什么。
bitset本质上可以看作是一个数组,不过每一位只能是0或1,即一个支持位运算的二进制数组 这个题目中我们定义了两个bitset容器dp和tep。dp保存上一次所有的S值,tmp保存这一轮所有的S值,并将dp[0]的的初始值设为1,方便之后的转移。就下来就是递推公式的推导了了。
1.在这个题目中,可以用bitset容器来保存数字。记录每一个数字的平方是否可以存在。 2.外层循环代表n个区间的遍历,内层循环用来表示遍历一个区间中所有可能取到的值。 3.每次转移与要用到位运算<<和|,因为在区间里增加上了一个平方的可能取值,这意味着tmp容器要更新当前s的值。而只需要dp<<j*j就可以表示上一次的s值增加了新的量,在进行或运算就消除了相同的结果,存进了tmp中。(不过对于为什么左移多少位就代表增加我还没有想的特别清楚) 那么转移如下:for(int j=l;j<=r;j++) tmp|=dp<<jj;
代码:
#include#define INF 0x3f3f3f3f;//const int maxn=;using namespace std;typedef long long ll;bitset<1000005>dp,tmp;int main (){ //freopen("D:\\input.txt", "r", stdin); //freopen("D:\\output.txt", "w", stdout); int n,l,r; cin>>n; dp[0]=1; for(int i=1;i<=n;i++){ cin>>l>>r; tmp.reset(); for(int j=l;j<=r;j++) tmp|=dp<
转载地址:https://blog.csdn.net/u011612364/article/details/106226407 如侵犯您的版权,请留言回复原文章的地址,我们会给您删除此文章,给您带来不便请您谅解!
发表评论
最新留言
很好
[***.229.124.182]2023年11月12日 01时33分37秒
关于作者

喝酒易醉,品茶养心,人生如梦,品茶悟道,何以解忧?唯有杜康!
-- 愿君每日到此一游!
推荐文章
[PAT]1043 Is It a Binary Search Tree (25 分)
2019-03-28
[LeetCode]1278. Palindrome Partitioning III
2019-03-28
[pyqt] 实现窗口嵌套
2019-03-28
[pyqt] 使用自定义QListWidgetItem
2019-03-28
[CMake] cmake入门: 调用多个目录下的源文件
2019-03-28
[csdn] 解决csdn网页离线后打开自动跳转到csdn主页
2019-03-28
[论文]知网下载pdf&&caj转pdf
2019-03-28
[dp]双蛋问题&&李永乐老师视频
2019-03-28
[PAT]1103 Integer Factorization (30分)
2019-03-28
[PAT]1091 Acute Stroke (30分)(样例5未过原因)
2019-03-28
[KD-Tree] KD Tree
2019-03-28
[CLion] 设置快捷输入当前时间
2019-03-28
机器学习监督学习之分类算法---朴素贝叶斯代码实践
2019-03-28
黑马程序员C++学习笔记(第一阶段:基础)
2019-03-28
黑马程序员C++学习笔记(第二阶段核心:面向对象)(二)
2019-03-28