题目链接
题意 给出n*m的方格，有些格子不能铺线，其它格子必须铺，形成一个闭合回路。问有多少种铺法？
思路 比赛时基本做不出来，就学个新算法玩玩。
学习链接
代码对于我这个不会hash_table 的不太友好，先自己封装了一个用着舒服的hash_table，当然也可以直接用STL里的 unordered_map，初学算法我认为直接使用后者更好，循序渐进。
插头dp简单的说还是轮廓线的状压dp？，多考虑了一种连通性问题。
用括号表示法表示轮廓线后，然后考虑状态转移。
枚举每点，考虑左边的朝右插头 r，上边朝下插头 d，左插头1表示，右插头2表示
- if 当前点是障碍
- else if (!r && !d)
- else if (r && !d)
- else if (!r && d)
- else if (r == 1 && d == 1)
- else if (r == 2 && d == 2)
- else if (r == 1 && d == 2)
- else if (r == 2 && d == 1)
一个坑点
| ^ 运算符优先级不同，不是从左到右运算，然后找了半天bug，还是用 + - 比较稳。代码 STL unordered_map
代码
991ms
吸氧后 228ms
#include
using namespace std;
#define ll long longunordered_map dp[3];
// chatou 0 null, 1 right, 2 down
ll n, m, endx, endy, a[15][15], bit[15];
#define prel (1ll<>bit[j])&3ll;
ll r = (sta>>bit[j-1])&3ll;
//printf("%lld %lld - %lld %lld\n",i,j,sta,w);
//printf("%lld = %lld\n\n",r,d);
if(!a[i][j]) {
if(!r && !d) dp[cur][sta] += w;
}
else if(!r && !d) {
if(a[i+1][j] && a[i][j+1]) dp[cur][sta + prel + (2*prer)] += w;
}
else if(r && !d) {
if(a[i+1][j]) dp[cur][sta] += w;
if(a[i][j+1]) dp[cur][sta - (r*prel) + (r*prer)] += w;
}
else if(!r && d) {
if(a[i+1][j]) dp[cur][sta + (d*prel) - (d*prer)] += w;
if(a[i][j+1]) dp[cur][sta] += w;
}
else if(r == 1 && d == 1) {
ll cnt = 1;
for(ll p = j+1;
p <= m;
++p) {
if(((sta>>bit[p])&3ll) == 1) ++cnt;
if(((sta>>bit[p])&3ll) == 2) --cnt;
if(!cnt) {
dp[cur][(sta - (r*prel) - (d*prer)) - (1<= 0;
--p) {
if(((sta>>bit[p])&3ll) == 1) --cnt;
if(((sta>>bit[p])&3ll) == 2) ++cnt;
if(!cnt) {
dp[cur][(sta - (r*prel) - (d*prer)) + (1< 【洛谷 P5056 【模板】插头dp】手写hash_table
代码
577ms
吸氧后 562ms
#include
using namespace std;
#define ll long longstruct hash_table {
ll hash_mod = 590027;
ll state[600000], ans[600000], up;
ll tot, first[600000], nxt[600000], w[600000];
void init() {
memset(first, 0, sizeof(first));
tot = 0;
up = 0;
}
ll ins(ll sta, ll val) {
ll key = sta%hash_mod;
for(ll i = first[key];
i;
i = nxt[i]) {
if(state[w[i]] == sta) return ans[w[i]] += val;
}
state[++up] = sta;
ans[up] = val;
nxt[++tot] = first[key];
w[tot] = up;
first[key] = tot;
return val;
}
}dp[2];
/*hash_table*/
// chatou 0 null, 1 right, 2 down
ll n, m, endx, endy, a[15][15], bit[15];
#define prel (1ll<>bit[j])&3ll;
ll r = (sta>>bit[j-1])&3ll;
//printf("%lld %lld - %lld %lld\n",i,j,sta,w);
//printf("%lld = %lld\n\n",r,d);
if(!a[i][j]) {
if(!r && !d) dp[cur].ins(sta,w);
}
else if(!r && !d) {
if(a[i+1][j] && a[i][j+1]) dp[cur].ins(sta + prel + (2*prer),w);
}
else if(r && !d) {
if(a[i+1][j]) dp[cur].ins(sta,w);
if(a[i][j+1]) dp[cur].ins(sta - (r*prel) + (r*prer),w);
}
else if(!r && d) {
if(a[i+1][j]) dp[cur].ins(sta + (d*prel) - (d*prer),w);
if(a[i][j+1]) dp[cur].ins(sta,w);
}
else if(r == 1 && d == 1) {
ll cnt = 1;
for(ll p = j+1;
p <= m;
++p) {
if(((sta>>bit[p])&3ll) == 1) ++cnt;
if(((sta>>bit[p])&3ll) == 2) --cnt;
if(!cnt) {
dp[cur].ins((sta - (r*prel) - (d*prer)) - (1<= 0;
--p) {
if(((sta>>bit[p])&3ll) == 1) --cnt;
if(((sta>>bit[p])&3ll) == 2) ++cnt;
if(!cnt) {
dp[cur].ins((sta - (r*prel) - (d*prer)) + (1< 
