关灯问题II 洛谷2622

https://www.luogu.org/problemnew/show/P2622

状态压缩DP

设$f(state)$表示当前开的灯是$state$时，关掉这些灯需要的最少步数

转移则是

#f(state)=min_{i=1}^m {f(buttons[i].operate(state))+1}#

代码

#include <iostream>
#include <algorithm>
#include <string>
#include <cinttypes>
using int_t = long long int;

using std::cin;
using std::cout;
using std::endl;

int_t n, m;
std::string binary(int_t x, int_t size);
struct Button
{
uint32_t on;
uint32_t off = (~0);
inline int_t operate(int_t state)
{
// cout << "state " << binary(state, n) << " opted = " << binary(state & off | on, n) << endl;
return (state & off) | on;
}
} buttons[101];

// int_t search(int_t state)
// {
// static int_t memory[1030];
// static bool visited[1030];
// static bool visiting[1030];

// if (state == 0)
// return 0;
// visiting[state] = true;
// if (visited[state])
// {
// return memory[state];
// }
// int_t result = 0x7ffffffffll;
// for (int_t i = 1; i <= m; i++)
// {
// auto temp = buttons[i].operate(state);
// if (visiting[temp])
// continue;
// // auto result = ;
// // cout << "searching state " << binary(temp, n) << " result = " << search(temp) << endl;
// result = std::min(result, search(temp) + 1);
// }
// visiting[state] = false;
// if (result == 0)
// {
// return 0x7ffffffffll;
// }
// visited[state] = true;
// return memory[state] = result;
// }

std::string binary(int_t x, int_t size)
{
std::string result;
for (int_t i = size - 1; i >= 0; i--)
{
result += (((x & (1 << i)) != 0) + '0');
}
return result;
}
int main()
{
cin >> n >> m;
for (int_t i = 1; i <= m; i++)
{
auto &button = buttons[i];
for (int_t j = 0; j < n; j++)
{
int_t opt;
cin >> opt;
if (opt == -1)
{
button.off ^= (1 << (j));
}
else if (opt == 1)
{
button.on |= (1 << (j));
}
}
// cout << "button " << i << " on:" << binary(button.on, n) << " off:" << binary(button.off, n) << endl;
}
static int_t dp[1030];
std::fill(dp + 1, dp + (1 << n), 0x7fffffff);

for (int_t i = 0; i < (1 << n); i++)
{
for (int_t j = 1; j <= m; j++)
{
auto &button = buttons[j];
auto state = button.operate(i);
dp[state] = std::min(dp[state], dp[i] + 1);
}
}
auto result = dp[(1 << n) - 1];
if (result >= 0x7fffffff)
cout << -1;
else
cout << result << endl;
return 0;
}