题意 :给定n个灯,m个开关, 以及每个开关的效果, 要求灭掉所有的灯至少需要多少次
>> face <<
Strategy:状压DP, i是一个表示二进制的十进制数,'1’表示开灯
状态: dp[i] 达到状态’i’ 最少需要多少次
目标: dp[0] -> 全灭
边界: dp[(1 << n) - 1 ] = 1 ;其余全部初始成无穷
合法判断: 默认所有状态合法
转移方程:
d
p
[
i
]
=
m
i
n
(
d
p
[
i
]
,
d
p
[
j
]
+
1
)
dp[i] = min(dp[i], dp[j] + 1)
dp[i]=min(dp[i],dp[j]+1)
attention: 倒叙枚举
双倍经验: 注意枚举的边界, 位运算的优先级 (判断某一位是否是0不能用xor)
#include <bits/stdc++.h>
#define _rep(i, a, b) for (int i = (a); i <= (b); ++i)
#define _rev(i, a, b) for (int i = (a); i >= (b); --i)
#define _for(i, a, b) for (int i = (a); i < (b); ++i)
#define _rof(i, a, b) for (int i = (a); i > (b); --i)
#define ll long long
#define all(x) x.begin(), x.end()
#define db double
#define eps 0.00001
#define met(a, b) memset(a, b, sizeof(a))
#define lowbit(x) x &(-x)
#define cost first
#define what_is(x) cerr << #x << " is " << x << endl;
#define val second
#define oo 0x3f3f3f3f
#define pi acos(-1.0)
using namespace std
;
const int maxn
= 1 << 11;
int dp
[maxn
];
int matrix
[103][12];
int main()
{
int n
, m
;
cin
>> n
>> m
;
_rep(i
, 1, m
)
{
_rep(j
, 1, n
)
{
cin
>> matrix
[i
][j
];
}
}
memset(dp
, oo
, sizeof(dp
));
dp
[(1 << n
) - 1] = 0;
_rev(i
, (1 << n
) - 1, 0)
{
_rep(j
, 1, m
)
{
int state
= i
;
_rep(k
, 1, n
)
{
if (matrix
[j
][k
] == 0)
continue;
if (matrix
[j
][k
] == 1 && ((i
>> (k
- 1)) & 1))
{
state
^= 1 << (k
- 1);
}
if (matrix
[j
][k
] == -1 && !((i
>> (k
- 1)) & 1))
{
state
^= 1 << (k
- 1);
}
}
dp
[state
] = min(dp
[state
], dp
[i
] + 1);
}
}
printf("%d\n", dp
[0] == oo
? -1 : dp
[0]);
}
