hdu - 4979 - A simple math problem.（可重复覆盖DLX + 打表）
栏目：互联网时间：2014-11-03 08:18:24
题意：1种彩票共有 N 个号码，每注包括 M 个号码，如果开出来的 M 个号码中与自己买的注有 R 个以上的相同号码，则中2等奖，问要保证中2等奖最少要买多少注(1<=R<=M<=N<=8)。
题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=4979
――>>覆盖问题，yy可知是可重复覆盖问题，因而，DLX 上场。。
N个 选 R 个，共有 C[N][R] 种选法，每种选法需要被覆盖，对应于 DLX 中的列。。
N个 选 M 个，共有 C[N][M] 种选法，每种选法对应于 DLX 中的行。。
8 x 8 x 8 的大小，还可以打个表。。我的机子上打此表用时870s，约15分钟。。
所以。。不打表，测试数据又严谨的话，准过不了。。曾我想在比赛时开1个终端让程序打表比较长的时间，今天遇到了。。
核心：
#include <cstdio>
#include <cstring>
const int MAXN = 8;
const int MAXR = 1000;
const int MAXC = 1000;
const int MAXNODE = MAXR * MAXC;
const int INF = 0x3f3f3f3f;
int stateInCol[MAXC], ccnt;
int rcnt;
int bitcnt[1 << MAXN];
int C[MAXN + 1][MAXN + 1];
struct DLX
{
int sz;
int H[MAXR], S[MAXC];
int row[MAXNODE], col[MAXNODE];
int U[MAXNODE], D[MAXNODE], L[MAXNODE], R[MAXNODE];
int Min;
void Init(int n)
{
for (int i = 0; i <= n; ++i)
{
U[i] = D[i] = i;
L[i] = i - 1;
R[i] = i + 1;
}
L[0] = n;
R[n] = 0;
sz = n + 1;
memset(S, 0, sizeof(S));
memset(H, ⑴, sizeof(H));
}
void Link(const int& r, const int& c)
{
row[sz] = r;
col[sz] = c;
D[sz] = D[c];
U[D[c]] = sz;
D[c] = sz;
U[sz] = c;
if (H[r] == ⑴)
{
H[r] = L[sz] = R[sz] = sz;
}
else
{
R[sz] = R[H[r]];
L[R[H[r]]] = sz;
R[H[r]] = sz;
L[sz] = H[r];
}
S[c]++;
sz++;
}
void Remove(const int& c)
{
for (int i = D[c]; i != c; i = D[i])
{
L[R[i]] = L[i];
R[L[i]] = R[i];
}
}
void Restore(const int& c)
{
for (int i = U[c]; i != c; i = U[i])
{
L[R[i]] = i;
R[L[i]] = i;
}
}
int A()
{
int ret = 0;
bool vis[MAXC];
memset(vis, 0, sizeof(vis));
for (int i = R[0]; i != 0; i = R[i])
{
if (!vis[i])
{
vis[i] = true;
++ret;
for (int j = D[i]; j != i; j = D[j])
{
for (int k = R[j]; k != j; k = R[k])
{
vis[col[k]] = true;
}
}
}
}
return ret;
}
void Dfs(int cur)
{
if (cur + A() >= Min) return;
if (R[0] == 0)
{
if (cur < Min)
{
Min = cur;
}
return;
}
int c = R[0];
for (int i = R[0]; i != 0; i = R[i])
{
if (S[i] < S[c])
{
c = i;
}
}
for (int i = D[c]; i != c; i = D[i])
{
Remove(i);
for (int j = R[i]; j != i; j = R[j])
{
Remove(j);
}
Dfs(cur + 1);
for (int j = L[i]; j != i; j = L[j])
{
Restore(j);
}
Restore(i);
}
}
int Solve()
{
Min = INF;
Dfs(0);
return Min;
}
} dlx;
int Bitcnt(int x)
{
int ret = 0;
while (x)
{
ret += (x & 1);
x >>= 1;
}
return ret;
}
void GetBitcnt()
{
for (int i = 0; i < (1 << MAXN); ++i)
{
bitcnt[i] = Bitcnt(i);
}
}
void GetC()
{
for (int i = 1; i <= MAXN; ++i)
{
C[i][0] = C[i][i] = 1;
for (int j = 1; j < i; ++j)
{
C[i][j] = C[i - 1][j] + C[i - 1][j - 1];
}
}
}
void Init()
{
GetBitcnt();
GetC();
}
void Solve(int N, int M, int R)
{
ccnt = 0;
for (int i = 1; i < (1 << N); ++i)
{
if (bitcnt[i] == R)
{
stateInCol[i] = ++ccnt;
}
}
dlx.Init(C[N][R]);
rcnt = 0;
for (int i = 1; i < (1 << N); ++i)
{
if (bitcnt[i] == M)
{
++rcnt;
for (int j = i; j > 0; j = (i & (j - 1)))
{
if (bitcnt[j] == R)
{
dlx.Link(rcnt, stateInCol[j]);
}
}
}
}
printf("%d", dlx.Solve());
}
void SaveTable()
{
puts("{");
for (int N = 1; N <= MAXN; ++N)
{
puts(" {");
for (int M = 1; M <= N; ++M)
{
printf(" {");
for (int R = 1; R <= M; ++R)
{
if (R > 1)
{
printf(", ");
}
Solve(N, M, R);
}
printf("}");
if (M == N)
{
puts("");
}
else
{
puts(",");
}
}
printf(" }");
if (N == MAXN)
{
puts("");
}
else
{
puts(",");
}
}
puts("}");
}
int main()
{
freopen("table.txt", "w", stdout);
Init();
SaveTable();
return 0;
}
AC代码：
#include <cstdio>
const int MAXN = 8;
int ret[MAXN][MAXN][MAXN] = {
{
{1}
},
{
{2},
{1, 1}
},
{
{3},
{2, 3},
{1, 1, 1}
},
{
{4},
{2, 6},
{2, 3, 4},
{1, 1, 1, 1}
},
{
{5},
{3, 10},
{2, 4, 10},
{2, 3, 4, 5},
{1, 1, 1, 1, 1}
},
{
{6},
{3, 15},
{2, 6, 20},
{2, 3, 6, 15},
{2, 3, 4, 5, 6},
{1, 1, 1, 1, 1, 1}
},
{
{7},
{4, 21},
{3, 7, 35},
{2, 5, 12, 35},
{2, 3, 5, 9, 21},
{2, 3, 4, 5, 6, 7},
{1, 1, 1, 1, 1, 1, 1}
},
{
{8},
{4, 28},
{3, 11, 56},
{2, 6, 14, 70},
{2, 4, 8, 20, 56},
{2, 3, 4, 7, 12, 28},
{2, 3, 4, 5, 6, 7, 8},
{1, 1, 1, 1, 1, 1, 1, 1}
}
};
int main()
{
int T, N, M, R, kase = 0;
scanf("%d", &T);
while (T--)
{
scanf("%d%d%d", &N, &M, &R);
printf("Case #%d: %d
", ++kase, ret[N - 1][M - 1][R - 1]);
}
return 0;
}
------分隔线----------------------------
------分隔线----------------------------