首页 > 代码库 > BZOJ 2064: 分裂 [DP 状压 转化]
BZOJ 2064: 分裂 [DP 状压 转化]
传送门
题意：一开始$n$块面积最后$m$块面积，面积和相等每次可以分裂或者合并，问最少几次
昨天忘发了...
不会....
考虑最差情况，$n+m-2$所有先合并再分裂
发现只有当前后两个子集相等时可以变成对方
如果前后能分成$k$堆对应相等，次数就是$n+m-2*k$
问题就是求前后各能分成几堆面积相等
混在一起，后面的面积改为负
$f[i]$表示选了集合$i$里的土地，能分成几个互不相交的权值为$0$的子集
$f[i]=max{f[i^(1<<j)]}+ sum[i]==0 $
因为$0-0=0$
#include <iostream>#include <cstdio>#include <cstring>#include <algorithm>#include <cmath>using namespace std;typedef long long ll;const int N=(1<<20)+5;inline int read(){ char c=getchar();int x=0,f=1; while(c<‘0‘||c>‘9‘){if(c==‘-‘)f=-1;c=getchar();} while(c>=‘0‘&&c<=‘9‘){x=x*10+c-‘0‘;c=getchar();} return x*f;} int n,m,f[N],sum[N],All;int main(){ //freopen("in","r",stdin); n=read(); for(int i=0;i<n;i++) sum[1<<i]=read(); m=read(); for(int i=n;i<n+m;i++) sum[1<<i]=-read(); All=1<<(n+m); for(int i=1;i<All;i++){ int lowbit=i&-i; sum[i]=sum[i-lowbit]+sum[lowbit]; for(int j=0;j<n+m;j++) if(i&(1<<(j-1))) f[i]=max(f[i],f[i-(1<<(j-1))]); f[i]+= sum[i]==0; } printf("%d",n+m-2*f[All-1]);}
BZOJ 2064: 分裂 [DP 状压 转化]
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。