main pri return for cor code lds amp next
题目大意:
给你一个m*n的01矩阵,请你搞一些破坏。
你可以选择搞坏任意一个数字为1的格子。
如果格子上的数字为0,它本来就是坏的,不用管它。
为了掩人耳目,你搞坏的格子不能直接相邻(即不能有公共边),不包括原来就坏掉的格子。
问有多少种搞破坏的方案。
思路:
状压DP。
f[i][j]表示第i行状态为j的方案数。
我们可以枚举当前行的状态j和上一行的状态k,并判断是否合法。
简单来说就是判断状态中是否有相邻的格子,是否有和上一行重复的,是否有本来就坏掉的格子。
然后直接暴力转移即可。
- #include < cstdio > #include < cctype > #include < cstring > #include < algorithm > inline int getint() {
- register char ch;
- while (!isdigit(ch = getchar()));
- register int x = ch ^ ‘0‘;
- while (isdigit(ch = getchar())) x = (((x << 2) + x) << 1) + (ch ^ ‘0‘);
- return x;
- }
- const int mod = 1e8,
- inf = 0x7fffffff;
- const int M = 12;
- int a[2];
- int f[2][1 << M];
- int main() {
- const int m = getint(),
- n = getint();
- for (register int i = 0; i < m; i++) {
- a[i & 1] = 0;
- memset(f[i & 1], 0, sizeof * f);
- for (register int j = 0; j < n; j++) {
- if (getint()) a[i & 1] |= 1 << j;
- }
- for (register int j = 0; j < (1 << n); j++) {
- for (register int t = 1; t < n; t++) {
- if ((j & (1 << t)) && (j & (1 << (t - 1)))) goto Next_j;
- }
- if ((a[i & 1] | j) != a[i & 1]) continue;
- if (!i) {
- f[i & 1][j] = 1;
- continue;
- }
- for (register int k = 0; k < (1 << n); k++) {
- for (register int t = 1; t < n; t++) {
- if ((k & (1 << t)) && (k & (1 << (t - 1)))) goto Next_k;
- }
- if ((a[!(i & 1)] | k) != a[!(i & 1)]) continue;
- if (j & k) continue;
- f[i & 1][j] = (f[i & 1][j] + f[!(i & 1)][k]) % mod;
- Next_k: ;
- }
- Next_j: ;
- }
- }
- int ans = 0;
- for (register int i = 0; i < (1 << n); i++) {
- ans = (ans + f[!(m & 1)][i]) % mod;
- }
- printf("%d\n", ans);
- return 0;
- }
[USACO06NOV]Corn Fields
来源: http://www.bubuko.com/infodetail-2368476.html