[APIO2015]巴厘岛的雕塑[按位贪心+dp]

2021-07-03 10:10

阅读：557

标签：bit get eof fine api efi sdi 方法 include

题意

给你长度为 \(n\) 的序列，要求分成 \(k\) 段连续非空的区间，求所有区间和的 \(or\) 最小值。

分析

定义 \(f_{i,j}\) 表示前 \(i\) 个点分成 \(j\) 段的最小 \(or\) 是有问题的，因为可能有一位一定在后面出现而某一位没有必要在后面出现，这时贪心就出现了问题。
考虑按位贪心，假设考虑到了第 \(b\) 位，定义 \(f_{i,j}\) 表示前 \(i\) 个点分成 \(j\) 段且满足 \(b\) 以上位的限制，第 \(b\) 位为 \(0\) 是否存在方案。如果这一位没有方法满足为 \(0\) 就设置成 \(1\).
复杂度 \(O(60*n^3)\)
对于最后一个 \(subtask\) 稍微改一下定义即可,复杂度 \(O(60*n^2)\)。

代码

#include
using namespace std;
#define go(u) for(int i=head[u],v=e[i].to;i;i=e[i].lst,v=e[i].to)
#define rep(i,a,b) for(int i=a;iinline bool Max(T &a,T b){return ainline bool Min(T &a,T b){return b>b+1 | (s[i]-s[k]>>b+1)) ==res>>b+1  && !((s[i]-s[k]>>b)&1))
            Min(f[i],f[k]+1);
            if(f[n]!=inf&&f[n]>b+1 | (s[i]-s[k]>>b+1)) ==res>>b+1  && !((s[i]-s[k]>>b)&1));
            }
            bool fg=0;
            for(int i=A;i

[APIO2015]巴厘岛的雕塑[按位贪心+dp]

标签：bit get eof fine api efi sdi 方法 include

原文地址：https://www.cnblogs.com/yqgAKIOI/p/9900181.html

上一篇：Linux中的exec和source有什么区别呢？

下一篇：rabbitmq安装(windows)

文章来自：搜素材网的编程语言模块，转载请注明文章出处。
文章标题：[APIO2015]巴厘岛的雕塑[按位贪心+dp]
文章链接：http://soscw.com/index.php/essay/101207.html

亲，登录后才可以留言！

[APIO2015]巴厘岛的雕塑[按位贪心+dp]

题意

分析

代码

评论

热门文章

推荐文章

最新文章

置顶文章