插头DP
插头的定义：
对于两个连通的块，如图所示，对于((1,1))和((2,1))，我们称((1,1))有一个下插头，((2,1))有一个上插头
对于此图则为一个闭环。
轮廓线的定义：
如图所示，对于(n imes m)的网格，对于我们(egin{aligned}mathcal{DP}end{aligned})到的一个格子，我们都可以画出如图所示的一条线语文能力太差不会描述，这条画出来的线就叫轮廓线，这条线的作用是分割已经(egin{aligned}mathcal{DP}end{aligned})过的区域和没有(egin{aligned}mathcal{DP}end{aligned})过的区域。轮廓线的具体用途为存储已有的(egin{aligned}mathcal{DP}end{aligned})状态。
(egin{aligned}mathcal{DP}end{aligned})的主体思路：那所以插头(egin{aligned}mathcal{DP}end{aligned})到底要(egin{aligned}mathcal{DP}end{aligned})的是什么？我们可以理解为目前(egin{aligned}mathcal{DP}end{aligned})到的格子的插头的状态，记录目前插头的状态所对应的方案数。何为插头状态，就是插头存在不存在，指向上下还是左右。对于不同的题我们可能在(egin{aligned}mathcal{DP}end{aligned})过程中处理的细节不一样，我们插头代表的意义可能有所不同，但总体的(egin{aligned}mathcal{DP}end{aligned})过程中插头的处理方法大致是一样的。
对于此图就是我们在(egin{aligned}mathcal{DP}end{aligned})过程中的例子，对于此格我们改变的只是在这个格子周围的状态，对于格子之外的位置的状态并未改变，我们不用关注，跨过此格之后的轮廓线的J和J+1相对位置如图所示，我们关注的就是这J和J+1位置的插头有无，是否连通，方向
给出 (n imes m) 的方格，有些格子不能铺线，其它格子必须铺，形成一个闭合回路。问有多少种铺法？
我们设(dp[i][j][s])为(egin{aligned}mathcal{DP}end{aligned})到格子(egin{aligned}(i,j)end{aligned})，插头状态为s的方案数是多少，对于s我们使用四进制数来存储状态
由轮廓线的上图我们可以发现，对于我们目前(egin{aligned}mathcal{DP}end{aligned})到的格子，我们首先要考虑格子的左方和上方的连通性，再来考虑右方和下方的连通性
对于左方和上方的状态，我们对应到轮廓线上是第J个位置和第J+1个位置，同时我们(egin{aligned}mathcal{DP}end{aligned})到的此格我们一定会有一进一出，对于小编号的位置我们设定相对位置为左，大编号的位置我们设定相对位置为右，存储在s则是没有为0，左为1，右为2
为什么不用三进制，你会闲的没事来写一个进制优化吗？能白嫖不香吗
Type1：左闭上闭
考虑此格的下格和右格子是否是连通的，是连通的话我们就让他开创新的插头，并用我们的规定，让其J位置的插头方向为左，J+1位置插头方向为右
Type2：左闭上开
对于上方我们的轮廓线位置是J+1，我们考虑此格的下方和右方的连通性，若下格连通，即移动后相对位置的J是连通的，我们只需将J+1位置的插头抵消然后新开对于转移后轮廓线J位置的插头，若右方连通，即J+1位置连通，我们直接继承即可，同时对于插头的相对方向我们保持不变
Type3：左开上闭
对于上方我们的轮廓线位置是J，我们考虑此格的下方和右方的连通性，若右格连通，即移动后相对位置的J+1是连通的，我们只需将J位置的插头抵消然后新开对于转移后轮廓线J+1位置的插头，若下方连通，即J位置连通，我们直接继承即可，同时对于插头的相对方向我们保持不变
Type4：左开右开
对于此情况，因为我们对于一个格子只会存在一进一出，所以我们必定从这两个位置走，我们需要讨论这两个插头在其各自连通路径中的相对位置
1：左左上左
如图，我们对于此情况，在连接之后，J+1路径的右在连通之后变成了相对位置的左，J路径的右边的相对位置则相对位置不变，因此我们的操作就是消去上方左方的插头，并改变相对位置
2：左右上左
如图，我们对于此情况，在连接之后，J路径与J+1路径的相对左右没有发生改变，对此我们直接继承，并将两个插头消去
3：左左上右
对于此情况，这两个插头一定是属于同一条相对路径上的，因此在我们连接之后一定会形成一个闭合回路，对于此题题意，我们必定会在最后来连接这个回路，否则肯定会形成两个以上的回路不符合方案，遇到此情况就是我们要的答案
4：左右上右
如图，我们对于此情况，在连接之后，J+1路径的左在连通之后相对位置不变，J路径的左在连通后变成了相对位置的右，因此我们的操作就是消去上方左方的插头，并改变相对位置
然后我们会发现在转移的时候我们只是在用([i][j])和([i][j+1])的位置，因此我们可以考虑滚动数组，然后我们考虑对于重复的状态会增加复杂度，因此我们使用来优(egin{aligned}mathcal{Hash}end{aligned})化，这样我们的空间大大缩小，时间复杂度为(O(nm imes 4^{m+1}))
#include<bits/stdc++.h>
#define LL long long
#define int long long
#define _ 0
using namespace std;
/*Grievous Lady*/
template <typename _n_> void mian(_n_ & _x_){
_x_ = 0;int _m_ = 1;char buf_ = getchar();
while(buf_ < '0' || buf_ > '9'){if(buf_ == '-')_m_ =- 1;buf_ = getchar();}
do{_x_ = _x_ * 10 + buf_ - '0';buf_ = getchar();}while(buf_ >= '0' && buf_ <= '9');_x_ *= _m_;
}
unordered_map<int , int> dp[2];
int n , m , endx , endy , mp[101][101];
char c;
inline int oqs(int x , int y){
return x << (y << 1);
}
inline int DP(){
int tmp = (1 << ((m + 1) << 1)) - 1;
int numnow = 0 , numnxt = 1;
dp[numnow][0] = 1;
for(int i = 1;i <= n;i ++){
for(int j = 1;j <= m;j ++){
dp[numnxt].clear();
for(auto k = dp[numnow].begin(); k != dp[numnow].end(); k ++){
int S = k -> first , val = k -> second;
int L = (S >> ((j - 1) << 1)) & 3 , R = (S >> (j << 1)) & 3;
if(!mp[i][j]){
if(!L && !R) dp[numnxt][S] += val;
continue;
}
if(!L && !R){
if(mp[i][j + 1] && mp[i + 1][j]) dp[numnxt][S ^ oqs(1 , j - 1) ^ oqs(2 , j)] += val;
}
if(!L && R){
if(mp[i][j + 1]) dp[numnxt][S] += val;
if(mp[i + 1][j]) dp[numnxt][S ^ oqs(R , j) ^ oqs(R , j - 1)] += val;
}
if(L && !R){
if(mp[i][j + 1]) dp[numnxt][S ^ oqs(L , j - 1) ^ oqs(L , j)] += val;
if(mp[i + 1][j]) dp[numnxt][S] += val;
}
if(L == R){
if(L == 1 && R == 1){
int nowar = 0;
for(int p = j ; ; p ++){
int dou = (S >> (p << 1)) & 3;
if(dou == 1) nowar ++;
if(dou == 2) nowar --;
if(nowar == 0){
dp[numnxt][S ^ oqs(L , j - 1) ^ oqs(R , j) ^ oqs(2 , p) ^ oqs(1 , p)] += val;
break;
}
}
}
if(L == 2 && R == 2){
int nowar = 0;
for(int p = j - 1; ; p --){
int dou = (S >> (p << 1)) & 3;
if(dou == 2) nowar ++;
if(dou == 1) nowar --;
if(nowar == 0){
dp[numnxt][S ^ oqs(L , j - 1) ^ oqs(R , j) ^ oqs(1 , p) ^ oqs(2 , p)] += val;
break;
}
}
}
}
if(L == 2 && R == 1){
dp[numnxt][S ^ oqs(L , j - 1) ^ oqs(R , j)] += val;
}
if(L == 1 && R == 2 && i == endx && j == endy){ return val; }
}
swap(numnow , numnxt);
}
dp[numnxt].clear();
for(auto k = dp[numnow].begin(); k != dp[numnow].end(); k ++){
dp[numnxt][(k -> first << 2) & tmp] += k -> second;
}
swap(numnxt , numnow);
}
return 0;
}
inline int Ame_(){
mian(n) , mian(m);
for(int i = 1;i <= n;i ++){
for(int j = 1;j <= m;j ++){
cin >> c;
if(c == '*') mp[i][j] = 0;
else if(c == '.') mp[i][j] = 1 , endx = i , endy = j;
}
}
printf("%lld
" , DP());
return ~~(0^_^0);
}
int Ame__ = Ame_();
signed main(){;}
板子题顺带写个高精__int128，顺带要记得方案数( imes 2)并且特判行和列为1时的情况即可
考虑如何定义插头，我们会发现插头只有两种状态，一种是拐弯，一种是不拐弯，那么我们就很好应对了
对于一个位置，我们用0代表没有插头，1代表有没拐弯的插头，2代表拐弯的插头
对此我们开始大力讨论
Type1：左闭上闭
对于此情况我们可以选择插入没拐弯的下插头，没拐弯的右插头以及一个拐弯的插头
Type2：左闭上开&&上=1
对于此情况，我们可以选择向下延伸，即J的位置有了一个没拐弯的插头，或者右边即J+1的位置有一个拐弯的插头
Type3：左开上闭&&左=1
对于此情况，我们可以选择向右延伸，即J+1的位置有了一个没拐弯的插头，或者J位置有一个拐弯的插头
Type4：左闭上开&&上=2
对于此情况，我们可以选择向下延伸，即J的位置有了一个没拐弯的插头，或者作为终点统计答案
Type5：左开上闭&&左=2
对于此情况，我们可以选择向右延伸，即J+1的位置有了一个没拐弯的插头，或者作为终点统计答案
Type6：左开上开
对于此情况有两种
1：左=1&&上=1
两个为拐弯的插头交汇变成拐弯的插头
2：左=2&&上=2
显然不存在
#include<bits/stdc++.h>
#define LL long long
#define _ 0
using namespace std;
/*Grievous Lady*/
template <typename _n_> void mian(_n_ & _x_){
_x_ = 0;int _m_ = 1;char buf_ = getchar();
while(buf_ < '0' || buf_ > '9'){if(buf_ == '-')_m_ =- 1;buf_ = getchar();}
do{_x_ = _x_ * 10 + buf_ - '0';buf_ = getchar();}while(buf_ >= '0' && buf_ <= '9');_x_ *= _m_;
}
#define int long long
#define mod 20110520
int r , c , endx , endy , mp[110][110] , tmp[110][110];
char chino;
unordered_map<int , LL> dp[2];
inline int oqs(int x , int y){
return x << (y << 1);
}
inline void add(int &x , int val){
x %= mod; (x += val) %= mod;
}
inline int DP(){
int tmp = (1 << ((c + 1) << 1)) - 1;
LL numnow = 0 , numnxt = 1 , ans = 0;
dp[numnow][0] = 1;
for(int i = 1;i <= r;i ++){
for(int j = 1;j <= c;j ++){
// cout << ans << '
';
dp[numnxt].clear();
for(auto k = dp[numnow].begin(); k != dp[numnow].end(); k ++){
int S = k -> first , val = k -> second;
int L = (S >> ((j - 1) << 1)) & 3 , R = (S >> (j << 1)) & 3;
if(!mp[i][j]){
if(!L && !R) add(dp[numnxt][S] , val);
continue;
}
if(!L && !R){
if(mp[i][j + 1]) add(dp[numnxt][S ^ oqs(1 , j)] , val);
if(mp[i + 1][j]) add(dp[numnxt][S ^ oqs(1 , j - 1)] , val);
if(mp[i][j + 1] && mp[i + 1][j]) add(dp[numnxt][S ^ oqs(2 , j) ^ oqs(2 , j - 1)] , val);
}
if(L && !R){
if(L == 1 && R == 0){
if(mp[i][j + 1]) add(dp[numnxt][S ^ oqs(L , j - 1) ^ oqs(1 , j)] , val);
if(mp[i + 1][j] && L == 1) add(dp[numnxt][S ^ oqs(L , j - 1) ^ oqs(2 , j - 1)] , val);
}
if(L == 2 && R == 0){
add(dp[numnxt][S ^ oqs(L , j - 1)] , val);
if(mp[i][j + 1]) add(dp[numnxt][S ^ oqs(L , j - 1) ^ oqs(2 , j)] , val);
}
}
if(!L && R){
if(L == 0 && R == 1){
if(mp[i + 1][j]) add(dp[numnxt][S ^ oqs(R , j) ^ oqs(R , j - 1)] , val);
if(mp[i][j + 1] && R == 1) add(dp[numnxt][S ^ oqs(R , j) ^ oqs(2 , j)] , val);
}
if(L == 0 && R == 2){
add(dp[numnxt][S ^ oqs(R , j)] , val);
if(mp[i + 1][j]) add(dp[numnxt][S ^ oqs(R , j - 1) ^ oqs(R , j)] , val);
}
}
if(L == 1 && R == 1){
add(dp[numnxt][S ^ oqs(L , j - 1) ^ oqs(R , j)] , val);
}
// if(i == endx && j == endy){
// if(L == 1 && R == 1) add(ans , val);
// if(L == 0 && R == 2) add(ans , val);
// if(L == 2 && R == 0) add(ans , val);
// // return val;
// }
}
swap(numnow , numnxt);
}
dp[numnxt].clear();
for(auto k = dp[numnow].begin(); k != dp[numnow].end(); k ++){
add(dp[numnxt][(k -> first << 2) & tmp] , k -> second);
}
swap(numnow , numnxt);
}
return dp[numnxt][0];
}
inline int Ame_(){
mian(r) , mian(c);
for(int i = 1;i <= r;i ++)
for(int j = 1;j <= c;j ++){
cin >> chino;
if(chino == '*') mp[i][j] = 0;
else if(chino == '_') mp[i][j] = 1 , endx = i , endy = j;
}
if(r < c){
for(int i = 1;i <= r;i ++)
for(int j = 1;j <= c;j ++)
tmp[j][i] = mp[i][j];
swap(r , c);
memset(mp , 0 , sizeof(mp));
for(int i = 1;i <= r;i ++)
for(int j = 1;j <= c;j ++)
mp[i][j] = tmp[i][j];
swap(endx , endy);
}
printf("%lld
" , DP());
return ~~(0^_^0);
}
int Ame__ = Ame_();
signed main(){;}
/*
3 3
___
_*_
___
*/
插头的状态和模板题一模一样，只需要更改更新答案的条件即可
#include<bits/stdc++.h>
#define LL long long
#define _ 0
using namespace std;
/*Grievous Lady*/
template <typename _n_> void mian(_n_ & _x_){
_x_ = 0;int _m_ = 1;char buf_ = getchar();
while(buf_ < '0' || buf_ > '9'){if(buf_ == '-')_m_ =- 1;buf_ = getchar();}
do{_x_ = _x_ * 10 + buf_ - '0';buf_ = getchar();}while(buf_ >= '0' && buf_ <= '9');_x_ *= _m_;
}
#define int long long
const int kato = 12 + 10;
inline int oqs(int x , int y){
return x << (y << 1);
}
unordered_map<int , int> dp[2];
int t , n , m , endx , endy , mp[kato][kato] , ans , tot;
inline int DP(){
dp[0].clear(); dp[1].clear();
int tmp = (1 << ((m + 1) << 1)) - 1;
int numnow = 0 , numnxt = 1;
dp[numnow][0] = 1;
for(int i = 1;i <= n;i ++){
for(int j = 1;j <= m;j ++){
dp[numnxt].clear();
for(auto k = dp[numnow].begin() ; k != dp[numnow].end(); k ++){
int S = k -> first , val = k -> second;
int L = (S >> ((j - 1) << 1)) & 3 , R = (S >> (j << 1)) & 3;
if(!mp[i][j]){
if(!L && !R) dp[numnxt][S] += val;
continue;
}
if(!L && !R){
if(mp[i][j + 1] && mp[i + 1][j]) dp[numnxt][S ^ oqs(1 , j - 1) ^ oqs(2 , j)] += val;
}
if(!L && R){
if(mp[i][j + 1]) dp[numnxt][S] += val;
if(mp[i + 1][j]) dp[numnxt][S ^ oqs(R , j) ^ oqs(R , j - 1)] += val;
}
if(L && !R){
if(mp[i][j + 1]) dp[numnxt][S ^ oqs(L , j - 1) ^ oqs(L , j)] += val;
if(mp[i + 1][j]) dp[numnxt][S] += val;
}
if(L == R){
if(L == 1 && R == 1){
int nowar = 0;
for(int p = j ; ; p ++){
int dou = (S >> (p << 1)) & 3;
if(dou == 1) nowar ++;
if(dou == 2) nowar --;
if(nowar == 0){
dp[numnxt][S ^ oqs(L , j - 1) ^ oqs(R , j) ^ oqs(2 , p) ^ oqs(1 , p)] += val;
break;
}
}
}
if(L == 2 && R == 2){
int nowar = 0;
for(int p = j - 1 ; ; p --){
int dou = (S >> (p << 1)) & 3;
if(dou == 1) nowar --;
if(dou == 2) nowar ++;
if(nowar == 0){
dp[numnxt][S ^ oqs(L , j - 1) ^ oqs(R , j) ^ oqs(1 , p) ^ oqs(2 , p)] += val;
break;
}
}
}
}
if(L == 1 && R == 2 && i == endx && j == endy){
ans += val;
}
if(L == 1 && R == 2 && ((i != endx) || (j != endy))){
dp[numnxt][S ^ oqs(L , j - 1) ^ oqs(R , j)] += val;
}
if(L == 2 && R == 1){
dp[numnxt][S ^ oqs(L , j - 1) ^ oqs(R , j)] += val;
}
}
swap(numnow , numnxt);
}
dp[numnxt].clear();
for(auto k = dp[numnow].begin() ; k != dp[numnow].end(); k ++){
dp[numnxt][(k -> first) << 2 & tmp] += k -> second;
}
swap(numnow , numnxt);
}
return ans;
}
inline int Ame_(){
mian(t);
for(; t --> 0 ;){
mian(n) , mian(m);
memset(mp , 0 , sizeof(mp));
ans = 0;
for(int i = 1;i <= n;i ++){
for(int j = 1;j <= m;j ++){
mian(mp[i][j]);
if(mp[i][j] == 1) endx = i , endy = j , tot ++;
}
}
if(tot > 0) tot = 0; else ans = 1;
printf("%lld
" , DP());
}
return ~~(0^_^0);
}
int Ame__ = Ame_();
signed main(){;}
依旧可以白嫖模板题的插头状态，但是对于(egin{aligned}mathcal{Hash}end{aligned})存储是第一次直接赋值，第二次之后再取(egin{aligned}mathcal{max}end{aligned})，这是个值得注意的点，其次对于L=1并且R=2形成闭合回路时，若其他地方没有插头则更新答案，否则情况不合法，不计入答案.
#include<bits/stdc++.h>
#define LL long long
#define _ 0
using namespace std;
/*Grievous Lady*/
template <typename _n_> void mian(_n_ & _x_){
_x_ = 0;int _m_ = 1;char buf_ = getchar();
while(buf_ < '0' || buf_ > '9'){if(buf_ == '-')_m_ =- 1;buf_ = getchar();}
do{_x_ = _x_ * 10 + buf_ - '0';buf_ = getchar();}while(buf_ >= '0' && buf_ <= '9');_x_ *= _m_;
}
#define INF 0x3f3f3f3f
#define get_max(x , y)
{
if(x == 0) x = y;
else x = max(x , y);
}
#define int long long
inline int oqs(int x , int y){
return x << (y << 1);
}
const int kato = 100 + 10;
int n , m , val[kato][kato];
unordered_map<int , LL> dp[2];
inline LL DP(){
int tmp = (1 << ((m + 1) << 1)) - 1;
LL numnow = 0 , numnxt = 1 , ans = -INF;
dp[numnow][0] = 0;
for(int i = 1;i <= n;i ++){
for(int j = 1;j <= m;j ++){
dp[numnxt].clear();
for(auto k = dp[numnow].begin(); k != dp[numnow].end(); k ++){
// cout << "QAQ" << '
';
int S = k -> first; LL last = k -> second;
LL now = last + val[i][j];
int L = (S >> ((j - 1) << 1)) & 3 , R = (S >> (j << 1)) & 3;
if(!L && !R){
if(i < n && j < m) get_max(dp[numnxt][S ^ oqs(1 , j - 1) ^ oqs(2 , j)] , now);
get_max(dp[numnxt][S] , last);
}
if(L && !R){
if(i < n) get_max(dp[numnxt][S] , now);
if(j < m) get_max(dp[numnxt][S ^ oqs(L , j - 1) ^ oqs(L , j)] , now);
}
if(!L && R){
if(i < n) get_max(dp[numnxt][S ^ oqs(R , j) ^ oqs(R , j - 1)] , now);
if(j < m) get_max(dp[numnxt][S] , now);
}
if(L == R){
if(L == 1 && R == 1){
int nowar = 0;
for(int p = j ; ; p ++){
int dou = (S >> (p << 1)) & 3;
if(dou == 1) nowar ++;
if(dou == 2) nowar --;
if(nowar == 0){
get_max(dp[numnxt][S ^ oqs(L , j - 1) ^ oqs(R , j) ^ oqs(2 , p) ^ oqs(1 , p)] , now);
break;
}
}
}
if(L == 2 && R == 2){
int nowar = 0;
for(int p = j - 1; ; p --){
int dou = (S >> (p << 1)) & 3;
if(dou == 2) nowar ++;
if(dou == 1) nowar --;
if(nowar == 0){
get_max(dp[numnxt][S ^ oqs(L , j - 1) ^ oqs(R , j) ^ oqs(1 , p) ^ oqs(2 , p)] , now);
break;
}
}
}
}
if(L == 2 && R == 1){
get_max(dp[numnxt][S ^ oqs(L , j - 1) ^ oqs(R , j)] , now);
}
if(L == 1 && R == 2 && (S ^ oqs(L , j - 1) ^ oqs(R , j)) == 0){ ans = max(ans , now); }
}
// cout << ans << '
';
swap(numnow , numnxt);
}
dp[numnxt].clear();
for(auto k = dp[numnow].begin(); k != dp[numnow].end(); k ++){
dp[numnxt][(k -> first << 2) & tmp] += k -> second;
}
swap(numnxt , numnow);
// cout << ans << '
';
}
return ans;
}
inline int Ame_(){
mian(n) , mian(m);
for(int i = 1;i <= n;i ++){
for(int j = 1;j <= m;j ++){
mian(val[i][j]);
}
}
printf("%lld
" , DP());
return ~~(0^_^0);
}
int Ame__ = Ame_();
signed main(){;}
/*
4 4
100 300 -400 400
-100 1000 1000 1000
-100 -100 -100 -100
-100 -100 -100 1000
*/
-----(egin{aligned}mathcal{Ame}end{aligned})__