UOJ Logo kczno1的博客

博客

bzoj3508

2017-11-29 14:29:06 By kczno1

定义数组$a:$$a[i]=1$表示最终第$i$个灯泡亮,$0$表示暗。

则操作相当于对$a$区间异或。

差分,即令$b[i]=a[i]$ $xor$ $a[i-1]$

则$a$的区间$[l,r]$异或等价于$b[l],b[r+1]$异或。

把所有$b[i]=1$的$i$拿出来,记作数组$q$

就是每次解决掉一对$q[i],q[j]$,代价为$g[q[j]-q[i]]$

( $g$可以$O(nl)$ $bfs$得到 )

状压$dp$,$O(2^{len}*len)$ ($len$为$q$的长度,$<=2*k$)

#include<bits/stdc++.h>
using namespace std;

typedef long long ll;
#define pb push_back
#define rep(i,l,r) for(int i=l;i<=r;++i)
#define per(i,r,l) for(int i=r;i>=l;--i)

template <typename T> inline void chmin(T &x,const T &y)
{
    if(x>y)x=y;
}
template <typename T> inline void chmax(T &x,const T &y)
{
    if(x<y)x=y;
}

#define gc (c=getchar())
int read()
{
    char c;
    while(gc<'-');
    if(c=='-')
    {
        int x=gc-'0';
        while(gc>='0')x=x*10+c-'0';
        return -x;
    }
    int x=c-'0';
    while(gc>='0')x=x*10+c-'0';
    return x;
}

const int N=1e4+5,L=100+5,K=10,inf=N*N;
int n,k,l;
int a[N],b[N],g[N];
int top,q[K*2];
int dp[1<<K*2];

namespace GET_G
{
int q[N];
int a[L];
void get()
{
    rep(i,1,l)a[i]=read();
    rep(i,1,n) g[i]=N;
    g[0]=0;
    int tail=1;
    q[1]=0;
    rep(head,1,tail)
    {
        int x=q[head];
        rep(i,1,l)
        {
            int y=x+a[i];
            if(y<=n&&g[y]==N) g[q[++tail]=y]=g[x]+1;
            y=x-a[i];
            if(y>0&&g[y]==N) g[q[++tail]=y]=g[x]+1;
        }
    }
}
};

int DP(int u)
{
    if(dp[u]!=-1)return dp[u];
    dp[u]=inf;
    int i=0;
    while(!(u&(1<<i))) ++i;
    rep(j,i+1,top-1)
    if(g[q[j]-q[i]]!=N)
    if(u&(1<<j)) chmin(dp[u],DP(u-(1<<i)-(1<<j))+g[q[j]-q[i]]);
    return dp[u];
}

int main()
{
    freopen("1.in","r",stdin);//freopen("1.out","w",stdout);
    int tt;
    cin>>tt;
    while(tt--)
    {
        cin>>n>>k>>l;

        memset(a,0,sizeof(a));
        rep(i,1,k)a[read()]=1;
        top=0;
        rep(i,1,n+1)
        if(a[i]^a[i-1])q[top++]=i;

        GET_G::get();

        int u=(1<<top)-1;
        memset(dp+1,-1,u*sizeof(int));
        dp[0]=0;
        DP(u);
        if(dp[u]==inf) puts("-1");
        else printf("%d\n",dp[u]);
    }
}

评论

zx2003
https://www.luogu.org/problemnew/show/3943这两道题是不是一样的啊?

发表评论

可以用@mike来提到mike这个用户,mike会被高亮显示。如果你真的想打“@”这个字符,请用“@@”。