本文主要是介绍[UVA10572]Black White 插头DP，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
多维护一个数来表示轮廓线上颜色的状态 用这个数的第m+1位来维护左上角的颜色信息
最后统计答案的时候要注意 这里要求的是一条路径而不是贿赂 所以允许最后一排存在至多一对独立插头(不同颜色不会同时存在独立插头 否则肯定不连通)
其他的玩意已经打在了代码的注释里面了
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<iostream>
#include<queue>
#define SF scanf
#define PF printf
#define bit(x) (1<<(x))
using namespace std;
typedef long long LL;
const int MAXNODE = 1000000;
const int MAXN = 8;
const int MOD = 233333;
int n, m, ex, ey, cur;
int a[MAXN+10], num[MAXN+10], pre[MAXN*MAXN+10][MOD+10];
char M[MAXN+10][MAXN+10], op[MAXN*MAXN+10][MOD+10];
struct Hash {int sz, adj[MOD+10], next[MOD+10];int sta[MOD+10], col[MOD+10], val[MOD+10];void clr() {memset(adj, -1, sizeof(adj));sz = 0;}void push(int s, int c, int v, int id, int fa, char OP) {int ss = s % MOD ;for(int i = adj[ss]; ~i; i = next[i])if(sta[i] == s && col[i] == c) {val[i] += v;return ;}sta[sz] = s; col[sz] = c; val[sz] = v;pre[id][sz] = fa; op[id][sz] = OP;next[sz] = adj[ss], adj[ss] = sz++;}
} dp[2];
void decode(int s) {for(int i = m-1; i >= 0; i--) a[i] = s & 7, s >>= 3;
}
int encode() {memset(num, -1, sizeof(num));int k = -1;int ret = 0;for(int i = 0; i < m; i++) {if(num[a[i]] == -1) num[a[i]] = ++k;ret = (ret << 3) | num[a[i]];}return ret;
}
void change(int x, int y) {for(int i = 0; i < m; i++) if(a[i] == x) a[i] = y;
}
void DP(int i, int j, int c) {for(int k = 0; k < dp[cur].sz; k++) {int cc = dp[cur].col[k];int U = i ? (cc >> j & 1) == c : 0;int L = j ? (cc >> (j-1) & 1) == c : 0;int LU = (cc >> m) == c;if(U && L && LU) continue;if(i == n-1 && j == m-1 && !U && !L && LU) continue;decode(dp[cur].sta[k]);if(i && !U) {int s1 = 0, s2 = 0;for(int t = 0; t < m; t++) {if(a[t] == a[j]) s1++; // 出现了单独的联通块 剩下的部分一定为相反颜色if((cc >> t & 1) != c) s2++;}if(s1 == 1) {if(s2 > 1) continue; // 如果不是全为相反颜色 则肯定不连通if(i < n-1 || j < m-2) continue; // 如果不为右下角两个格子 那么肯定会出现2*2中只有一种颜色的情况 }}if(U && L) { // 合并联通块if(a[j] != a[j-1]) change(a[j], a[j-1]);}else if(!U && L) a[j] = a[j-1]; // 延续联通块else if(!U && !L) a[j] = m;if(cc & (1 << j)) cc |= 1 << m; // 记录左上角颜色else cc &= ~(1 << m);if(c) cc |= 1 << j; // 更改当前颜色else cc &= ~(1 << j);dp[cur^1].push(encode(), cc, dp[cur].val[k], i*m+j, k, c ? '#' : 'o');}
}
void print(int k) {for(int i = n-1; i >= 0; i--)for(int j = m-1; j >= 0; j--) {M[i][j] = op[i*m+j][k];k = pre[i*m+j][k];}for(int i = 0; i < n; i++) puts(M[i]);
}
void solve() {cur = 0; dp[0].clr(); dp[0].push(0, 0, 1, 0, 0, 0);for(int i = 0; i < n; i++)for(int j = 0; j < m; j++) {dp[cur^1].clr();if(M[i][j] != '#') DP(i, j, 0);if(M[i][j] != 'o') DP(i, j, 1);cur ^= 1;}int ret = 0, k;for(int i = 0; i < dp[cur].sz; i++) {int MAX = 0;decode(dp[cur].sta[i]);for(int j = 0; j < m; j++) MAX = max(MAX, a[j]);if(MAX > 1) continue;ret += dp[cur].val[i];k = i;}PF("%d\n", ret);if(ret) print(k);
}
int main() {int _T; SF("%d", &_T); while(_T--) {SF("%d%d", &n, &m);memset(M, 0, sizeof(M));for(int i = 0; i < n; i++)for(int j = 0; j < m; j++)SF(" %c", &M[i][j]);solve();puts("");}
}
/*
1
6 8
........
........
........
........
.#......
........
*/这篇关于[UVA10572]Black White 插头DP的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
