首页 > 代码库 > Bzoj4069--Apio2015巴厘岛的雕塑
Bzoj4069--Apio2015巴厘岛的雕塑
题意 :
给你一个长度为n的数组y,和两个正整数a,b,让你把y分成a ~ b个连续区间,使每个区间的和或起来最小。
数据范围 :
subtask1 n<=100,1<=a<=b<=n,0<=y<=1e9
subtask2 n<=2000,a=1,1<=b<=n,0<=y<=1e9
---------------------------------------此后一千里------------------------------------------------
对于这一类求位运算最值问题,一般用的方法是按位贪心 ( 异或还可以线性基
我们要让最终答案最小,即从高到低位,能取0就取0
我们从高到低枚举二进制的位
然后问题就变成了对每一位在满足之前的位最小情况下该位能否取1
考虑dp去求
那么可以设定状态为dp[i][j]将前i个数分成j份,满足条件为1,不满足为0
若dp[i][j]为1,那么必需有一个k使dp[k][j-1]=1且sum[i]-sum[k]的前面几位为ans的前几位的子集且sum[i]-sum[k]的当前位为0
就可以枚举k,然后转移,复杂度O(n^3log)
观察第二个子任务的份数下限为1
那么我们没有了下限的限制,是不是如果满足条件的话取最小的份数就可以了呢?
所以直接把原dp状态的第二维去掉,加入dp值里,每次维护最小值
代码 :
#include<bits/stdc++.h> #define INF 0x3f3f3f3f #define low(x) ((x)&(-(x))) #define LL long long #define eps 1e-9 using namespace std; #define int int inline int Max(int a,int b) {return a>b?a:b;} inline int Min(int a,int b) {return a<b?a:b;} inline int Abs(int a) {return a>0?a:-a;} inline int Sqr(int a) {return a*a;} #undef int #define MAXN 2005 int n,a,b; LL ans,tmp,y[MAXN],g[MAXN];bool dp[105][105]; int main() { scanf("%d%d%d",&n,&a,&b); for(int i=1;i<=n;i++) scanf("%lld",&y[i]); for(int i=2;i<=n;i++) y[i]+=y[i-1]; for(int p=40;~p;p--) { bool ok=0; if(a==1) { for(int i=1;i<=n;i++) g[i]=INF; g[0]=0; for(int i=1;i<=n;i++) for(int j=0;j<i;j++) if((y[i]-y[j]&tmp|ans)==ans&&!(y[i]-y[j]>>p&1)) g[i]=Min(g[i],g[j]+1); if(g[n]>b) ans|=1ll<<p; } else { memset(dp,0,sizeof(dp));dp[0][0]=1; for(int j=1;j<=n;j++) for(int i=1;i<=n;i++) for(int k=0;k<i;k++) if(dp[k][j-1]&&((y[i]-y[k])&tmp|ans)<=ans&&!((y[i]-y[k])>>p&1)) { dp[i][j]=1;break; } for(int i=a;i<=b;i++) if(dp[n][i]) { ok=1;break; } if(!ok) ans|=1ll<<p; } tmp|=1ll<<p; } cout<<ans<<endl; return 0; }
Bzoj4069--Apio2015巴厘岛的雕塑
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。