A simple Blog for wyx I've been down the bottle hoping.
BZOJ 2064 分裂 状压$dp$
发表于: | 分类: Oi | 评论:0 | 阅读:39

做了一下宋爷的$dp$,感觉整个人都不是很好了
题目大意
给你两个序列,每次可以把上面的两个数变成一个数大小为两个数的和,也可以拆成两个加和等于他的数,现在问最少需要几次操作才能把他俩变成相同的序列

我们设上面的元素的个数是 $n$ 个,下面的个数是 $m$ 个。
首先最坏的情况一定是用 $n-1$ 次把上面的东西和在一起,然后再用 $m-1$ 次拆开,这个的次数是 $m+n-2$ ,然而这样并不是最优的
假设现在有了这样的情况,我们把上面的东西分成两坨,下面的东西分成两坨,这两坨分别对应相等,那么我们在吧他俩合并在一起的时候结束了,次数$-2$,而对于剩下的部分是递归同理的

现在的问题就变成了分别枚举上下两个东西的子集,然后求最大的相同子集的个数,当然这里的相等是指两个东西的权值和相同,假设这个值是 $k$ ,那么这个答案对应的就是 $n+m-2k$
你如果现在就暴力枚举的话加上一些奇怪的剪枝其实是可以的,但是不是非常的优美
我们可以把上面的 $n$ 个变成正数权值,下面的 $m$ 个变成负数权值,把初始的状态和结束的状态放在一起枚举。一个状态表示该物品取还是不取,用 $f(sta)$ 表示这个状态的所有子集中 $k$ 的最大值
如果 $sta$ 对应的值是0,说明两个子集完全相同 ,$f(sta)++$
最后
$$ans = m+n-2
f(Max),Max = 2^{(n+m)}-1$$

#include <stdio.h>
#include <string.h>
#include <iostream>
#include <algorithm>
#define lowbit(x) ((x)&(-x))
using namespace std;
const int Maxn = (1<<21)+5;
int F[Maxn],sum[Maxn];

inline int read()
{
    int x=0,f=1;char ch = getchar();
    while(ch < '0' || ch > '9'){if(ch == '-')f=-1;ch = getchar();}
    while(ch >='0' && ch <='9'){x=(x<<1)+(x<<3)+ch-'0';ch = getchar();}
    return x*f;
}

int main()
{
    int n = read();for(int i=1;i<=n;++i) sum[1<<(i-1)] = read();
    int m = read();for(int i=1;i<=m;++i) sum[1<<(i+n-1)] = -read();
    n += m;
    int Max = (1<<n) - 1;
    for(int i=1;i<=Max;++i)
    {
        int x = lowbit(i);
        sum[i] = sum[x] + sum[i^x];
        for(int j=0;j<n;++j)
            if(i&(1<<j))
                F[i] = max(F[i],F[i^(1<<j)]);
        if(!sum[i]) F[i]++;
    }
    cout << n - 2*F[Max];
}

Title - Artist
0:00

站点地图 网站地图
Copyright © 2015-2017 A simple Blog for wyx
Powered by Typecho自豪的采用Sgreen主题

TOP