http://acm.pku.edu.cn/JudgeOnline/problem?id=1185
Код:
#include <iostream> using namespace std; #define out(x) (cout << #x << ": " << x << endl) typedef long long int64; const int maxint = 0x7FFFFFFF; const int64 maxint64 = 0x7FFFFFFFFFFFFFFFLL; template <class T> void show(T a, int n) { for (int i = 0; i < n; ++i) cout << a[i] << ' '; cout << endl; } template <class T> void show(T a, int r, int l) { for (int i = 0; i < r; ++i) show(a[i], l); cout << endl; } const int maxn = 110; const int maxm = 11; const int mask[] = {1, 3, 9, 27, 81, 243, 729, 2187, 6561, 19683, 59049, 177147, 531441, 1594323}; int n, m; int g[maxn][maxm]; int f[maxn][59049]; int ok_state[10000]; int len; int bits[14]; inline int get_bit(int x, int k) { return x % mask[k + 1] / mask[k]; } void dfs(int origin_state, int origin_line, int now_col, int delta) { if (now_col >= m) { int new_state = 0; for (int i = 0; i < m; i++) if (bits[i] > 0) new_state += bits[i] * mask[i]; f[origin_line + 1][new_state] >?= f[origin_line][origin_state] + delta; return; } if (bits[now_col] == -1 && g[origin_line + 1][now_col] == 0) { bits[now_col] = 2; dfs(origin_state, origin_line, now_col + 3, delta + 1); bits[now_col] = -1; } dfs(origin_state, origin_line, now_col + 1, delta); } void dfs1(int now_col, int new_state, int last1, int last2) { if (now_col >= m) { ok_state[len++] = new_state; return; } if (last1 != 2 && last2 != 2) dfs1(now_col + 1, new_state + 2 * mask[now_col], 2, last1); if (last1 != 1 && last2 != 1) dfs1(now_col + 1, new_state + mask[now_col], 1, last1); dfs1(now_col + 1, new_state, 0, last1); } void pre_process() { len = 0; dfs1(0, 0, -1, -1); } int dp() { memset(f, -1, sizeof(f)); f[0][0] = 0; for (int i = 0; i < n; i++) { for (int j = 0; j < len; j++) if (f[i][ok_state[j]] != -1) { for (int k = 0; k < m; k++) bits[k] = get_bit(ok_state[j], k) - 1; dfs(ok_state[j], i, 0, 0); } } int ret = 0; for (int i = 0; i < mask[m]; i++) ret >?= f[n][i]; return ret; } int main() { char s[22]; scanf("%d%d", &n, &m); for (int i = 1; i <= n; i++) { scanf("%s", s); for (int j = 0; j < m; j++) if (s[j] == 'P') g[i][j] = 0; else g[i][j] = 1; } pre_process(); printf("%d\n", dp()); return 0; }