参考: https://www.cnblogs.com/liu-runda/p/6019426.html
有点神奇
大概就是显然最直观的转移是全部合起来再一个一个拆, 是 n+m 次, 然后设 f[i][j] 为分别取 i,j 状态的最多相同大小块的集合数, 枚举新加块转移, 答案是 n+m-2*f[(1<<n)-1][(1<<m)-1]
原因是体积和相同的两个快可以自己转移, 不用再和别的块合并一下
- #include<iostream>
- #include<cstdio>
- using namespace std;
- const int N=2005;
- int n,m,ln,lm,a[N],b[N],sa[N],sb[N],f[N][N];
- int main()
- {
- scanf("%d",&n);
- for(int i=0;i<n;i++)
- {
- scanf("%d",&a[i]);
- sa[1<<i]=a[i];
- }
- scanf("%d",&m);
- for(int i=0;i<m;i++)
- {
- scanf("%d",&b[i]);
- sb[1<<i]=b[i];
- }
- ln=1<<n,lm=1<<m;
- for(int i=1;i<ln;i++)
- sa[i]=sa[i^(i&(-i))]+sa[i&(-i)];
- for(int i=1;i<lm;i++)
- sb[i]=sb[i^(i&(-i))]+sb[i&(-i)];
- for(int i=1;i<ln;i++)
- for(int j=1;j<lm;j++)
- {
- for(int k=0;k<n;k++)
- if(i&(1<<k))
- f[i][j]=max(f[i][j],f[i^(1<<k)][j]);
- for(int k=0;k<m;k++)
- if(j&(1<<k))
- f[i][j]=max(f[i][j],f[i][j^(1<<k)]);
- if(sa[i]==sb[j])
- f[i][j]++;
- }
- printf("%d\n",n+m-2*f[ln-1][lm-1]);
- return 0;
- }
来源: http://www.bubuko.com/infodetail-2821426.html