建一个收费网站 怎么收费,网站推广服务报价表,甜蜜蜜西瓜视频免费观看,网站虚拟主机 会计处理正题
题目链接:https://www.luogu.com.cn/problem/P5056 题目大意 n∗mn*mn∗m的网格#xff0c;求有多少条回路可以铺满整个棋盘。 解题思路
插头dpdpdp的#xff0c;写法是按照题解上的写法。
状态用的是括号匹配#xff0c;然后用了哈希邻接表#xff08;挂表#x…正题
题目链接:https://www.luogu.com.cn/problem/P5056 题目大意
n∗mn*mn∗m的网格求有多少条回路可以铺满整个棋盘。 解题思路
插头dpdpdp的写法是按照题解上的写法。
状态用的是括号匹配然后用了哈希邻接表挂表还有滚动数组优化空间
然后可以看题解学 code
#includecstdio
#includecstring
#includealgorithm
using namespace std;
const int P133331;
struct node{int to,next;
}a[P*2];
int n,m,o,tot,zx,zy,t[2],bit[25],ls[P],S[2][P],v[25][25];
long long ans,dp[2][P];
char st[25];
void Add(int s,long long v){int xs%P;for(int ils[x];i;ia[i].next)if(S[o][a[i].to]s){dp[o][a[i].to]v;return;}t[o];dp[o][t[o]]v;S[o][t[o]]s;a[tot].tot[o];a[tot].nextls[x];ls[x]tot;return;
}
int main()
{scanf(%d%d,n,m);for(int i1;in;i){scanf(%s,st1);for(int j1;jm;j)if(st[j].){v[i][j]1;zxi;zyj;}}for(int i0;i12;i)bit[i](1(i1));t[o]1;S[o][1]0;dp[o][1]1;for(int i1;in;i){for(int j1;jt[o];j)S[o][j]2;//将右插头移到最左边 for(int j1;jm;j){o^1;tott[o]0;memset(ls,0,sizeof(ls));int s,dpl,rpl;long long w;for(int k1;kt[!o];k){sS[!o][k];wdp[!o][k];dpl(s(j1))%4;rpl(s(j-11))%4;if(!v[i][j]){//障碍 if(!dpl !rpl)Add(s,w);//不能有插头 }else if(!dpl !rpl){//两边都没有插头if(v[i1][j]v[i][j1])//开一个左上角插头 Add(s2*bit[j]bit[j-1],w);} else if(!dpl rpl){//只有右插头 if(v[i1][j])Add(s,w);if(v[i][j1])Add(s-rpl*bit[j-1]rpl*bit[j],w);}else if(dpl !rpl){//只有下插头if(v[i1][j])Add(s-dpl*bit[j]dpl*bit[j-1],w);if(v[i][j1])Add(s,w); }else if(dpl1rpl1){int c1;for(int pj1;pm;p){if((s(p1))%41)c;if((s(p1))%42)c--;if(!c){Add(s-bit[j]-bit[j-1]-bit[p],w);break;}}}else if(dpl2rpl2){int c1;for(int pj-2;p0;p--){if((s(p1))%42)c;if((s(p1))%41)c--;if(!c){Add(s-2*bit[j]-2*bit[j-1]bit[p],w);break;}}}else if(dpl1rpl2)Add(s-2*bit[j-1]-bit[j],w);else if(dpl2rpl1)if(izxjzy)answ;}}}printf(%lld\n,ans);return 0;
}
