首页 > 代码库 > hdu4979 A simple math problem.

hdu4979 A simple math problem.

题意n选m彩票中,至少买几张彩票保证至少能中r个数.

产生两个组合s1=c(n,m)和s2=c(n,r),题意就是从s1选取最少的组合数的并集包含所有s2.

然后就是建立一个矩阵,跑一个dlx.

----------------------------------------------------------------------------------------

#include <cstdio>
#include <cstring>
#define N 100
int n,m,r,cnt,tot;
int mustHas[N+20][9];
bool mat[N][N];
int a[10];
void dfs1(int k){
    if (k>r){
        cnt++;
        for (int i=1;i<=r;i++){
            mustHas[cnt][i] = a[i];
        }
        return ;
    }
    for (int i=a[k-1]+1;i<=n;i++){
        a[k] = i;
        dfs1(k+1);
        a[k] = 0;
    }
}
void dfs2(int k){
    if (k>m){
        tot++;
        for (int i=1;i<=cnt;i++){
            int num = 0;
            for (int j=1;j<=r;j++){
                for (int p=1;p<=m;p++){
                    if (mustHas[i][j]==a[p]){
                        num++;
                        break;
                    }
                }
            }
            if (num<r) continue;
            mat[tot][i] = true;
        }
        return ;
    }
    for (int i=a[k-1]+1;i<=n;i++){
        a[k] = i;
        dfs2(k+1);
        a[k] = 0;
    }
}
struct DLX{
    int U[N*N],D[N*N],L[N*N],R[N*N],siz[N*N],col[N*N],vist[N*N];
    int last,n,m,ans;
    void init(int nn,int mm){
        memset(U,0,sizeof(U));
        memset(D,0,sizeof(D));
        memset(L,0,sizeof(L));
        memset(R,0,sizeof(R));
        memset(siz,0,sizeof(siz));
        memset(col,0,sizeof(col));
        n = nn, m = mm;
        for (int i=0;i<=m;i++){
            L[i] = i - 1;
            R[i] = i + 1;
            U[i] = i;
            D[i] = i;
        }
        L[0] = m ; R[m] = 0;
        for (int i=m+1;i<=m+n;i++){
            L[i] = i;
            R[i] = i;
        }
        last = n + m;
        ans = N;
    }
    void add(int x,int y){
        last++;
        L[last] = L[x+m];
        R[last] = x+m;
        L[R[last]] = last;
        R[L[last]] = last;
        U[last] = U[y];
        D[last] = y;
        U[D[last]] = last;
        D[U[last]] = last;
        col[last] = y;
        siz[y]++;
    }
    void remove(int x){
        for (int i=D[x];i!=x;i=D[i]){
            R[L[i]] = R[i];
            L[R[i]] = L[i];
        }
    }
    void resume(int x){
        for (int i=U[x];i!=x;i=U[i]){
            R[L[i]] = L[R[i]] = i;
        }
    }
    int g(){
        memset(vist,0,sizeof(vist));
        int res = 0;
        while (1){
            int k = -1;
            for (int i=R[0];i;i=R[i]){
                if (!vist[i]&&siz[i]>0){
                    k = i;
                    break;
                }
            }
            if (k==-1) break;
            vist[k] = true;
            res++;
            for (int i=D[k];i!=k;i=D[i]){
                for (int j=R[i];j!=i;j=R[j]){
                    if (j<=m+n) continue;
                    vist[col[j]] = true;
                }
            }
        }
        return res;
    }
    void dfs(int k){
        if (k+g()>=ans) return;
        if (!R[0]) {
            if (k<ans) ans = k;
            return ;
        }
        int mn = N*N,x = -1;
        for (int i=R[0];i;i=R[i]){
            if (siz[i]<mn&&siz[i]>0){
                mn = siz[i];
                x = i;
            }
        }
        if (x==-1) return;
        for (int i=D[x];i!=x;i=D[i]){
            if (i<=m+n) continue;
            remove(i);
            for (int j=R[i];j!=i;j=R[j]){
                if (j<=m+n) continue;
                remove(j);
            }
            dfs(k+1);
            for (int j=L[i];j!=i;j=L[j]){
                if (j<=m+n) continue;
                resume(j);
            }
            resume(i);
        }
    }
}dlx;
int main(){
    int t;
    freopen("d:\\1.txt","a+",stdout);
    int p = 0;
    //for (scanf("%d",&t);t;t--){
            //scanf("%d%d%d",&n,&m,&r);
        for ( n=8;n<=8;n++)
            for ( m=1;m<=n;m++)
                for ( r=1;r<=m;r++){
        memset(mustHas,sizeof(mustHas),0);
        cnt = 0;
        dfs1(1);
        memset(mat,0,sizeof(mat));
        tot = 0;
        dfs2(1);
        dlx.init(tot,cnt);
        for (int i=1;i<=tot;i++){
            for (int j=1;j<=cnt;j++){
                if (mat[i][j]) dlx.add(i,j);
            }
        }
        dlx.dfs(0);
        printf("f[%d][%d][%d]=%d;\n",n,m,r,dlx.ans);
    }
    return 0;
}

------------------------------------------------------------------------------------

表如下:

f[1][1][1]=1;
f[2][1][1]=2;
f[2][2][1]=1;
f[2][2][2]=1;
f[3][1][1]=3;
f[3][2][1]=2;
f[3][2][2]=3;
f[3][3][1]=1;
f[3][3][2]=1;
f[3][3][3]=1;
f[4][1][1]=4;
f[4][2][1]=2;
f[4][2][2]=6;
f[4][3][1]=2;
f[4][3][2]=3;
f[4][3][3]=4;
f[4][4][1]=1;
f[4][4][2]=1;
f[4][4][3]=1;
f[4][4][4]=1;
f[5][1][1]=5;
f[5][2][1]=3;
f[5][2][2]=10;
f[5][3][1]=2;
f[5][3][2]=4;
f[5][3][3]=10;
f[5][4][1]=2;
f[5][4][2]=3;
f[5][4][3]=4;
f[5][4][4]=5;
f[5][5][1]=1;
f[5][5][2]=1;
f[5][5][3]=1;
f[5][5][4]=1;
f[5][5][5]=1;
f[6][1][1]=6;
f[6][2][1]=3;
f[6][2][2]=15;
f[6][3][1]=2;
f[6][3][2]=6;
f[6][3][3]=20;
f[6][4][1]=2;
f[6][4][2]=3;
f[6][4][3]=6;
f[6][4][4]=15;
f[6][5][1]=2;
f[6][5][2]=3;
f[6][5][3]=4;
f[6][5][4]=5;
f[6][5][5]=6;
f[6][6][1]=1;
f[6][6][2]=1;
f[6][6][3]=1;
f[6][6][4]=1;
f[6][6][5]=1;
f[6][6][6]=1;
f[7][1][1]=7;
f[7][2][1]=4;
f[7][2][2]=21;
f[7][3][1]=3;
f[7][3][2]=7;
f[7][3][3]=35;
f[7][4][1]=2;
f[7][4][2]=5;
f[7][4][3]=12;
f[7][4][4]=35;
f[7][5][1]=2;
f[7][5][2]=3;
f[7][5][3]=5;
f[7][5][4]=9;
f[7][5][5]=21;
f[7][6][1]=2;
f[7][6][2]=3;
f[7][6][3]=4;
f[7][6][4]=5;
f[7][6][5]=6;
f[7][6][6]=7;
f[7][7][1]=1;
f[7][7][2]=1;
f[7][7][3]=1;
f[7][7][4]=1;
f[7][7][5]=1;
f[7][7][6]=1;
f[7][7][7]=1;
f[8][1][1]=8;
f[8][2][1]=4;
f[8][2][2]=28;
f[8][3][1]=3;
f[8][3][2]=11;
f[8][3][3]=56;
f[8][4][1]=2;
f[8][4][2]=6;
f[8][4][3]=14;
f[8][4][4]=70;
f[8][5][1]=2;
f[8][5][2]=4;
f[8][5][3]=8;
f[8][1][1]=8;
f[8][2][1]=4;
f[8][2][2]=28;
f[8][3][1]=3;
f[8][3][2]=11;
f[8][3][3]=56;
f[8][4][1]=2;
f[8][4][2]=6;
f[8][4][3]=14;
f[8][4][4]=70;
f[8][5][1]=2;
f[8][5][2]=4;
f[8][5][3]=8;
f[8][1][1]=8;
f[8][2][1]=4;
f[8][2][2]=28;
f[8][3][1]=3;
f[8][1][1]=8;
f[8][2][1]=4;
f[8][2][2]=28;
f[8][3][1]=3;
f[8][3][2]=11;
f[8][3][3]=56;
f[8][4][1]=2;
f[8][4][2]=6;
f[8][4][3]=14;
f[8][4][4]=70;
f[8][5][1]=2;
f[8][5][2]=4;
f[8][5][3]=8;
f[8][5][4]=20;
f[8][5][5]=56;
f[8][6][1]=2;
f[8][6][2]=3;
f[8][6][3]=4;
f[8][6][4]=7;
f[8][6][5]=12;
f[8][6][6]=28;
f[8][7][1]=2;
f[8][7][2]=3;
f[8][7][3]=4;
f[8][7][4]=5;
f[8][7][5]=6;
f[8][7][6]=7;
f[8][7][7]=8;
f[8][8][1]=1;
f[8][8][2]=1;
f[8][8][3]=1;
f[8][8][4]=1;
f[8][8][5]=1;
f[8][8][6]=1;
f[8][8][7]=1;
f[8][8][8]=1;

hdu4979 A simple math problem.