HDU 3335 Divisibility dancing links 重复覆盖

分析：

dlx重复覆盖的巧用，重复覆盖的原理恰好符合本题的筛选方式，即选择一个数后，该数的倍数或约数可以保证在之后的搜索中不会被选择

于是修改一下启发函数，求解最大的重复覆盖即可。

 

其实不一定不被选择，只是选择以后，要么达不成目标，要不达到目标，也不如不选择更优

 

举下面的例子

3

2 3 6

答案一看就是 2

初始的dancing links的表示是这样的

      2   3   6

2    1   0   1

3    0   1   1

6    1   1   1

然后肯定先选第一列进行删

删 第一行时

 

得到

     2   3   6

2    0   0   0

3    0   1   0

6    0   1   0

此时要么删第二行，要么删第三行，所以6对应的第三行也是可以选的，只是选了第三行，对答案没有影响

 

#include<cstdio>

#include<cstring>

#include<queue>

#include<cstdlib>

#include<algorithm>

#include<vector>

#include<cmath>

using namespace std;

typedef long long LL;

const int N=1e6+;

const double eps=1e-;

int n,m,sz,k;

int u[N],l[N],r[N],d[N];

int h[],s[],col[N];

void init()

{

    for(int i=; i<=m; ++i)

    {

        s[i]=;

        u[i]=d[i]=i;

        l[i]=i-;

        r[i]=i+;

    }

    r[m]=;

    l[]=m;

    sz=m;

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

        h[i]=-;

}

void link(int x,int y)

{

    ++sz;

    ++s[y],col[sz]=y;

    u[sz]=u[y],d[u[y]]=sz;

    d[sz]=y,u[y]=sz;

    if(h[x]==-)h[x]=l[sz]=r[sz]=sz;

    {

        l[sz]=l[h[x]];

        r[l[h[x]]]=sz;

        r[sz]=h[x];

        l[h[x]]=sz;

    }

}

void del(int y)

{

    for(int i=d[y]; i!=y; i=d[i])

        r[l[i]]=r[i],l[r[i]]=l[i];

}

void resume(int y)

{

    for(int i=d[y]; i!=y; i=d[i])

        r[l[i]]=l[r[i]]=i;

}

int f()

{

    int ret=;

    for(int i=r[];i;i=r[i])++ret;

    return ret;

}

int ans;

void dance(int pos)

{

    if(pos+f()<=ans)return;

    if(!r[])

    {

        ans=max(pos,ans);

        return;

    }

    int t=r[];

    for(int i=r[]; i!=; i=r[i])

        if(s[i]<s[t])t=i;

    for(int i=d[t]; i!=t; i=d[i])

    {

        del(i);

        for(int j=r[i]; j!=i; j=r[j])

            del(j);

        dance(pos+);

        for(int j=l[i]; j!=i; j=l[j])

            resume(j);

        resume(i);

    }

}

LL a[];

int main()

{

    int T;

    scanf("%d",&T);

    while(T--)

    {

        scanf("%d",&n);

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

         scanf("%I64d",&a[i]);

       sort(a+,a++n);

       m=n;

       init();

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

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

          if(a[i]%a[j]==||a[j]%a[i]==)

            link(i,j);

       ans=;

       dance();

       printf("%d\n",ans);

    }

    return ;

}