BZOJ 2064: 分裂 状压动归
2024-10-21 16:29:49
最多的操作次数是 $n+m-1$ (相当于把第一个暴力合并,再暴力拆成第二个).
如果第一个序列的一个子序列和第二个区间的子序列相等,那么总次数就可以减 $2$.
将第二个序列所有数取反,直接求解有多少个子序列的和为 $0$ 即可
$ans=n+m-dp[1<<(n+m)-1]$
具体:
- $dp[i]=max(dp[i],dp[i xor (j<<1)])$
- $dp[i]=dp[i]+1, sum[i]=0$
#include<cstdio>
#include<algorithm>
using namespace std;
const int maxn=22;
int dp[1<<maxn],num[maxn],sum[1<<maxn];
int main()
{
freopen("in.txt","r",stdin);
int n,m,N;
scanf("%d",&n);
for(int i=1;i<=n;++i)scanf("%d",&num[i]);
scanf("%d",&m);
for(int i=n+1;i<=n+m;++i)
{
scanf("%d",&num[i]);
num[i]=-num[i];
}
N=n+m;
for(int i=1;i<(1<<N);++i)
{
sum[i]=0;
for(int j=1;j<=N;++j)
{
if(i&(1<<(j-1)) )
{
sum[i]+=num[j];
dp[i]=max(dp[i],dp[i^(1<<(j-1))]);
}
}
if(sum[i]==0)++dp[i];
}
printf("%d",n+m-2*dp[(1<<N)-1]);
return 0;
}
最新文章
- 10最好用的Node.js工具、插件和资料库
- css使一行文字竖向排列
- JS实现元素拖动
- python怎么装模块
- ubuntu 14.04 难用的vi
- Windows SEH学习 x86
- 移动WebApp开发框架(珍藏)
- hdu 5533 Dancing Stars on Me 水题
- 关于 Java Collections API 您不知道的 5 件事,第 1 部分
- NOTES : A Model of Gas Exchange for Hyperpolarized Xe(129) Magnetic Resonance of the Lung
- static的应用以及静态与非静态的区别
- python-pcap模块解析mac地址
- hdu Word Amalgamation(map)
- 2017年你需要一个VPN
- PHP获取文件扩展名的五种方式
- 您必须知道的 Git 分支开发规范
- emWin仪表界面设计,含uCOS-III和FreeRTOS两个版本
- luogu P1250 种树
- MySql实现分页查询的SQL,mysql实现分页查询的sql语句 (转)
- (59)Wangdao.com第十天_JavaScript 对象在 栈和堆