[BZOJ 2064]分裂

题解

这个题的思路异常地清奇...

首先看到数据范围很容易想到暴搜或者状压DP 2333

然后我们可以想到, 对于一个 $n$ 块的情况要想办法分裂合并为一个 $m$ 块的情况, 我们有保证可以分裂合并完成的策略: 通过 $n-1$ 次合并将面积合并为一整坨, 然后再通过 $m-1$ 次分裂将面积分为目标状态, 总操作数 $n+m-2$ . 然后我们需要想办法优化这个过程.

然后我们发现, 如果初始状态中挑出 $k_0$ 块的面积刚好等于目标状态中的 $k_1$ 块的面积, 我们可以单独让这几块通过 $k_0+k_1-2$ 次操作达到目标状态, 剩余的 $n-k_0$ 块与 $m-k_1$ 块可以通过 $n-k_0+m-k_1-2$ 次分裂合并达到目标状态, 总操作数会变为 $n+m-4$ 次.

也就是说我们如果每找到这样的一组对应关系, 就可以通过分组分裂合并减少 $2$ 次分裂合并的操作. 这样的组越多则所需操作数越少.

所以我们可以定义 $dp_i$ 为 $i$ 所代表的状态中的对应关系数的最大值. 另外再开一个辅助数组记录面积和来判断是否面积相等. 这里可以将目标状态的面积值定义为负, 这样就可以通过求和判断是否为 $0$ 来判定两块的面积是否相等了. 如果相等则说明找到了新一对对应关系(因为状态是唯一的).

至于转移, $dp_i$ 可以从状态 $i$ 任意减少一个元素后的状态转移. 取一下 $max$ 就好.

找到新一组对应关系后给 $dp$ 数组中对应该状态的值 $+1$ 就可以.

转移后得到的最终答案为 $n+m-2dp_{2^{n+m}-1}$ (因为每一对都减少了 $2$ . 整个整体也可以看成一对.)

参考代码

GitHub

 #include <cstdio>

 #include <cstring>

 #include <cstdlib>

 #include <iostream>

 #include <algorithm>

 const int MAXN=;

 int n;

 int n1,n2;

 int size[MAXN];

 int dp[<<MAXN];

 int sum[<<MAXN];

 int main(){

     scanf("%d",&n1);

     for(int i=;i<n1;i++){

         scanf("%d",size+i);

     }

     scanf("%d",&n2);

     for(int i=;i<n2;i++){

         scanf("%d",size+n1+i);

         size[n1+i]=-size[n1+i];

     }

     n=n1+n2;

     for(int i=;i<(<<n);i++){

         for(int j=;j<n;j++){

             if((i&(<<j))!=){

                 dp[i]=std::max(dp[i],dp[i^(<<j)]);

                 sum[i]+=size[j];

             }

         }

         if(sum[i]==)

             dp[i]++;

     }

     printf("%d\n",n-*dp[(<<n)-]);

     return ;

 }

Backup