题解 P3943 【星空】

· · 题解

差分是个常用的技巧，翻转连续的一段01序列很容易想到翻转异或差分序列上的两个数。

差分序列上最多有2k个1，并且肯定是偶数个。每次可以消除两个1，消除的代价与这两个1的距离相关，求将所有1消除的最小代价。

消除的代价用完全背包或者BFS都可以求出。用完全背包求消除代价，相当于把每个可以翻转的长度x，看做体积分别为x和-x的两个物品。

只有T\leq 2k\leq 16个需要翻转的1，直接状态压缩DP即可。

每次转移时可以先固定选择最小的位置，然后再枚举另一个位置。

时间复杂度\mathcal{O}(NM+2^T T)。

#include <cctype>
#include <cstdio>
#include <cstring>
#include <algorithm>
#define rep(i,x,y) for (int i=x; i<=y; ++i)
#define repd(i,x,y) for (int i=x; i>=y; --i)

int get()
{
    char c;
    while (!isdigit(c=getchar()));
    int k=c-'0';
    for (; isdigit(c=getchar()); k=k*10+c-'0');
    return k;
}

using namespace std;
const int N=4e4+10,S=1<<16|1;
int n,k,m,t,p[16],b[65],w[N],f[S],cnt[S],s;

int main()
{
    n=get()+1,k=get(),m=get();
    for (int i=k,j=-1,x; i--; j=x)
        if ((x=get())==j+1)
            p[t-1]=x+1;
        else
            p[t++]=x,p[t++]=x+1;
    memset(w,63,sizeof(w)),w[0]=0;
    rep(i,1,m)
        b[i]=get();
    rep(i,1,m)
        rep(j,b[i],n)
            w[j]=min(w[j],w[j-b[i]]+1);
    rep(i,1,m)
        repd(j,n-b[i],0)
            w[j]=min(w[j],w[j+b[i]]+1);
    memset(f,63,sizeof(f)),f[0]=0;
    s=(1<<t)-1;
    rep(i,1,s)
    {
        if ((cnt[i]=cnt[i>>1]+(i&1))&1)
            continue;
        int j=0,x;
        for (; !((i>>j)&1); ++j);
        x=i^(1<<j);
        rep(k,j+1,t-1)
            if ((x>>k)&1)
                f[i]=min(f[i],f[x^(1<<k)]+w[p[k]-p[j]]);
    }
    printf("%d",f[s]);
    return 0;
}

还可以用一般图最大权匹配做到\mathcal{O}(NM+T^3)。（大雾）