Description
背景: 和久必分, 分久必和... 题目描述: 中国历史上上分分和和次数非常多.. 通读中国历史的 WJMZBMR 表示毫无压力. 同时经常搞 OI 的他把这个变成了一个数学模型. 假设中国的国土总和是不变的. 每个国家都可以用他的国土面积代替, 又两种可能, 一种是两个国家合并为 1 个, 那么新国家的面积为两者之和. 一种是一个国家分裂为 2 个, 那么 2 个新国家的面积之和为原国家的面积. WJMZBMR 现在知道了很遥远的过去中国的状态, 又知道了中国现在的状态, 想知道至少要几次操作 (分裂和合并各算一次操作), 能让中国从当时状态到达现在的状态.
Input
第一行一个数 n1, 表示当时的块数, 接下来 n1 个数分别表示各块的面积. 第二行一个数 n2, 表示现在的块, 接下来 n2 个数分别表示各块的面积.
Output
一行一个数表示最小次数.
- Sample Input
- 1 6
- 3 1 2 3
- Sample Output
- 2
数据范围:
对于 100% 的数据, n1,n2<=10, 每个数 <=50
对于 30% 的数据, n1,n2<=6,
这状压的思路真是神仙啊......
首先, 最坏的情况就是把上面的合成一堆, 然后再分成下面的, 于是次数为 $n+m-2$
然后考虑如何减少次数. 如果上面的可以被合成 2 块, 下面的也可以合成 2 块, 且上下两块的值分别相等, 那么就可以减少一次合并和一次分开, 总次数减少了 2
于是发现如果上下可以被分成值相等的 $k$ 块, 那么总的次数是 $n+m-2*k$
然后现在就是要求 $k$ 的最大值了
我们用二进制表示某一个数选或不选. 如果一个数是上面的, 令它值为正, 下面的则值为负
然后如果上面的一块和下面的一块值对应相等的话, 就是所有的值加起来为 0
这样如果某一个子集的和为 0, 就说明它可以互相变化
于是令 $dp[i]$ 表示选的状态为 $i$ 时的最大的 $k$, 因为只有在 $sum[i]==0$ 时,$dp[i]++$, 其他状态都只能直接转移
- //minamoto
- #include<bits/stdc++.h>
- using namespace std;
- #define getc() (p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<21,stdin),p1==p2)?EOF:*p1++)
- char buf[1<<21],*p1=buf,*p2=buf;
- template<class T>inline bool cmax(T&a,const T&b){return a<b?a=b,1:0;}
- inline int read(){
- #define num ch-'0'
- char ch;bool flag=0;int res;
- while(!isdigit(ch=getc()))
- (ch=='-')&&(flag=true);
- for(res=num;isdigit(ch=getc());res=res*10+num);
- (flag)&&(res=-res);
- #undef num
- return res;
- }
- const int N=2e6+5;
- int n,m,sum[N],dp[N],lim;
- int main(){
- // freopen("testdata.in","r",stdin);
- n=read();for(int i=1;i<=n;++i) sum[1<<(i-1)]=read();
- m=read();for(int i=1;i<=m;++i) sum[1<<(i+n-1)]=-read();
- lim=1<<(n+m);
- for(int i=1;i<lim;++i){
- int tmp=i&-i;sum[i]=sum[tmp]+sum[i-tmp];
- for(int j=1;j<=n+m;++j)
- if(i&(1<<(j-1))) cmax(dp[i],dp[i-(1<<(j-1))]);
- if(!sum[i]) ++dp[i];
- }
- printf("%d\n",n+m-2*dp[lim-1]);
- return 0;
- }
来源: http://www.bubuko.com/infodetail-2807857.html