-
2019-10-07 01:48:14
先%mmh学长。
这个东西还好吧。。。。
也算是个状压,难的也不会,就会写个板子题。
用哈希map代替了哈希表。
一、P5056 【模板】插头dp:
题目背景
ural 1519陈丹琦《基于连通性状态压缩的动态规划问题》中的例题
题目描述
给出n*m的方格,有些格子不能铺线,其它格子必须铺,形成一个闭合回路。问有多少种铺法?输入格式
第1行,n,m(2<=n,m<=12)从第2行到第n+1行,每行一段字符串(m个字符),"*“表不能铺线,”."表必须铺
输出格式
输出一个整数,表示总方案数输入输出样例
输入 #1 复制
4 4
**…
…
…
…
输出 #1 复制
2
输入 #2 复制
4 4
…
…
…
…
输出 #2 复制
6#include<iostream> #include<cstdio> #include<algorithm> #include<cstring> #include<cmath> #include<string> #include<queue> #include<map> #include<unordered_map> #define ll long long #define llu unsigned ll using namespace std; const int maxn=20; const int maxx=2000100; const int mod=4; char str[maxn][maxn]; int pm[maxn][maxn],n,m,ex,ey; int b[maxn],bm[maxn]; int cnt[2],sta[2][maxx],k=0; unordered_map<int,ll>dp[2]; ll ans=0; void init(void) { for(int i=0;i<=13;i++) b[i]=(i<<1); for(int i=0;i<=13;i++) bm[i]=(1<<b[i]); } void in(int nowsta,ll sum) { if(dp[k].find(nowsta)==dp[k].end()) { sta[k][++cnt[k]]=nowsta; dp[k][nowsta]=sum; } else dp[k][nowsta]+=sum; } void DP(void) { cnt[k]=1; dp[k][0]=1; sta[k][1]=0; for(int i=1;i<=n;i++) { for(int j=1;j<=m;j++) { int p=k; k^=1; dp[k].clear(); cnt[k]=0; for(int cm=1;cm<=cnt[p];cm++) { int nowsta=sta[p][cm]; ll sum=dp[p][nowsta]; //上一行向下一行第一格转移时,没有右插头 if(j==1) nowsta<<=2; int r=(nowsta>>b[j-1])%mod; int d=(nowsta>>b[j])%mod; if(!pm[i][j]) { if(r==0&&d==0) in(nowsta,sum); } else if(r==0&&d==0) { if(pm[i+1][j]&&pm[i][j+1]) in(nowsta+bm[j-1]+2*bm[j],sum); } else if(r==0&&d!=0) { if(pm[i][j+1]) in(nowsta,sum); if(pm[i+1][j]) in(nowsta-d*bm[j]+d*bm[j-1],sum); } else if(r!=0&&d==0) { if(pm[i+1][j]) in(nowsta,sum); if(pm[i][j+1]) in(nowsta-r*bm[j-1]+r*bm[j],sum); } else if(r==1&&d==1) { int cc=1; for(int km=j+1;km<=m;km++) { if((nowsta>>b[km])%4==1) cc++; else if((nowsta>>b[km])%4==2) cc--; if(cc==0) { in(nowsta-bm[km]-bm[j]-bm[j-1],sum); break; } } } else if(r==2&&d==2) { int cc=1; for(int km=j-2;km>=0;km--) { if((nowsta>>b[km])%4==1) cc--; else if((nowsta>>b[km])%4==2) cc++; if(cc==0) { in(nowsta+bm[km]-2*bm[j]-2*bm[j-1],sum); break; } } } else if(r==2&&d==1) in(nowsta-2*bm[j-1]-bm[j],sum); else if(r==1&&d==2) if(ex==i&&ey==j) ans+=sum; } } } } int main(void) { init(); scanf("%d%d",&n,&m); for(int i=1;i<=n;i++) scanf("%s",str[i]+1); memset(pm,0,sizeof(pm)); for(int i=1;i<=n;i++) { for(int j=1;j<=m;j++) { if(str[i][j]=='.') pm[i][j]=1,ex=i,ey=j; } } DP(); printf("%lld\n",ans); return 0; }
二、P5074 Eat the Trees:
题目背景
HDU1693:Eat the Trees题目描述
给出n*m的方格,有些格子不能铺线,其它格子必须铺,可以形成多个闭合回路。问有多少种铺法?输入格式
每个测试点多组数据第一行一个正整数T,表示有T组数据
每组数据:
第1行,n,m(2<=n,m<=12)
从第2行到第n+1行,每行m个数字(1 or 0),1表铺线,0表不铺线
输出格式
每组数据输出一个整数(表方案数)输入输出样例
输入 #1 复制
2
6 3
1 1 1
1 0 1
1 1 1
1 1 1
1 0 1
1 1 1
2 4
1 1 1 1
1 1 1 1
输出 #1 复制
3
2因为本题允许有多个回路,所以不需要括号匹配。不再需要分析是左括号还是右括号。
状态:有插头设为1,无插头设为0。
状态转移与上题差不多,只是本题没有了左右括号的限制,可以随便接插头。#include<iostream> #include<cstdio> #include<algorithm> #include<cstring> #include<cmath> #include<string> #include<queue> #include<map> #include<unordered_map> #define ll long long #define llu unsigned ll using namespace std; const int maxn=15; int pm[maxn][maxn],n,m,cnt; ll dp[maxn][maxn][1<<maxn]; int bm[maxn]; void DP(void) { memset(dp,0,sizeof(dp)); dp[0][m][0]=1; for(int i=1;i<=n;i++) { for(int j=0;j<=cnt;j++) dp[i][0][j]=dp[i-1][m][j]; for(int j=1;j<=m;j++) { for(int cm=0;cm<=cnt;cm++) { int nowsta=cm; ll sum=dp[i][j-1][nowsta]; //上一行向下一行第一格转移时,没有右插头 if(j==1) nowsta<<=1; int r=(nowsta>>(j-1))&1; int d=(nowsta>>j)&1; if(!pm[i][j]) { if(r==0&&d==0) dp[i][j][nowsta]+=sum; } else if(r==0&&d==0) { if(pm[i+1][j]&&pm[i][j+1]) dp[i][j][nowsta+bm[j-1]+bm[j]]+=sum; } else if(r==0&&d!=0) { if(pm[i][j+1]) dp[i][j][nowsta]+=sum; if(pm[i+1][j]) dp[i][j][nowsta-bm[j]+bm[j-1]]+=sum; } else if(r!=0&&d==0) { if(pm[i+1][j]) dp[i][j][nowsta]+=sum; if(pm[i][j+1]) dp[i][j][nowsta-bm[j-1]+bm[j]]+=sum; } //允许有多个回路,其他情况直接接起来就好啦。 else dp[i][j][nowsta-bm[j-1]-bm[j]]+=sum; } } } printf("%lld\n",dp[n][m][0]); } int main(void) { for(int i=0;i<=13;i++) bm[i]=(1<<i); int t; scanf("%d",&t); while(t--) { scanf("%d%d",&n,&m); cnt=(1<<(m+1))-1; memset(pm,0,sizeof(pm)); for(int i=1;i<=n;i++) { for(int j=1;j<=m;j++) scanf("%d",&pm[i][j]); } DP(); } return 0; }
更多相关内容 -
NOIP基础-插头DP课件
2018-12-15 21:07:07NOIP基础内容学习-插头DP的精品课件,金牌选手打造,冲击NOIP必备 -
插头DP && 概率DP / 期望DP
2021-02-27 11:54:08插头DP && 概率DP / 期望DP写在前面:插头DPP5056 【模板】插头dp手写哈希表的方法:拉链法的代码如下:开放寻址法的代码如下:接下来是这道题的代码实现:P3190 [HNOI2007]神奇游乐园具体的代码实现如下:P...插头DP && 概率DP / 期望DP
写在前面:
快开学了,先发下最近整理的DP,还有过年前学的状压DP、记忆化搜索等基础DP还有图论等知识还在整理中…
由于本人平时比较懒,所以把十几道题都弄在一篇博客,这篇博客比较长,近3万字,但我相信大家还是能看懂我在说什么的。插头DP
P5056 【模板】插头dp
有些状压DP问题要求我们记录状态的连通性信息,这类问题一般被形象的称为插头DP或连通性状态压缩DP。插头dp是基于连通性状态压缩的动态规划,一般的适用范围:数据范围小,并且处于网格图中,对连通性有要求(要求选择出来的格子是一个连通块或者是一个路径/回路)。这样说起来很抽象,我先介绍一道插头dp的模板题:
给我们一个n * m的棋盘,这个棋盘里面有些格子是障碍,有些格子是空格,求这个棋盘有多少个不同的哈密顿回路(要经过每个格子,并且每个格子只能经过一遍),我们来简单回顾一下哈密顿回路的做法:先用一个状态S表示我们当前已经走过哪些点,另外用i表示我们当前走到了哪个点,然后枚举下一个点是哪一个点,假设下一个点是j,f(s, i)就变成了f(s | 1 << j, j),此时的时间复杂度是2n * n2,现在是一个棋盘,如果按照这种做法来做时间复杂度会太大。棋盘有个特点:每个格子只能和上下左右四个格子相连,并不是能和任意格子相连,所以可以按照一行一行来枚举所有状态(对于一般图我们就不能这样),我们递推的时候一般是按格来递推,举个例子,我们要考虑这个格子,这也意味着我们已经考虑完了这个红色线上方的格子,所以此时我们只要分析这个格子的状态就可以了。
因为我们要组成一个回路,所以每个格子只能有两条边会被经过,假设有一个边是进来的,有一个边是出去的,也就是在它的四条边里边选两条边经过,这样经过每个格子有6种情况,对于整一个连通块,我们只关心它轮廓线上的状态(即每条边有没有线经过),还要维护轮廓线上方部分的连通性(经过轮廓线的边哪些是属于同个连通块的)
(上面0和7,3和6就是属于同一个连通块)记录连通块一般有两种方法:1、最小表示法,从左往右遍历轮廓线,当遍历到没被标记的边(且有路径要经过它)的时候,按顺序标记,所以0和7标记成1,3和6标记成2(属于同个连通块标记相同),所以此时轮廓线的状态:10020021。2、括号表示法,括号表示法的适用范围要小一些,但效率更高(首选),因为我们要找的是一个哈密顿回路,这就意味着上半部分有一条边上去,就一定有一条边下来,这些边必然是两两配对的,而且这两条边之间的连通块是不可能交叉的(两条边所连的路径不可能交叉),因为是相邻的两两配对,所以可以看做是若干个括号,我们用1表示“左括号”,用2表示有括号,用一个三进制的数就能表示轮廓线的状态,所以此时轮廓线的状态:10010022。
这道题用括号表示法比用最小表示法的优势是,我们用012就可以表示轮廓线的状态,而最小表示法要用到的数可能很大(有多少个连通块,最大就是多少)。另外,括号表示法每一位就012,可以把它看成是4进制,然后在更新状态的时候就可以用位运算去优化。
状态表示是三维,f[i, j, s]表示当遍历到第i行第j列的格子的时候分界线的状态是s时,所有方案的数量,s有效的状态是4、5万个(因为它要满足1和2是两两配对的)。插头dp比较麻烦的就是状态转移,我们把目标格子(g[i, j])在轮廓线上的边标记成x和y,轮廓线上的状态为state,需要分成以下几种情况(转移的过程中x对应格子下面的边,y对应格子右边的边):
1、g[i, j]是障碍物,x和y一定是0,且这个格子也不会有路径经过,所以state不变(x和y都是0,转移之后也是0)
接下来g[i, j]不是障碍物的情况:
2、x和y均为0,更新后state中x = 1, y = 2
3、x为0,y非0,更新后state中状态不变或者x = y, y = 0
4、x非0,y为0,更新后state中y = x, x = 0或者状态不变
5、x = y = 1,x和y相连,此时state中原来x和y的位置变成0,然后离y最近的2变成1,又因为格子已经有两条边了,所以更新之后x和y对应的位置为0。
6、x = y = 2,x和y相连,此时state中原来x和y的位置变成0,然后离x最近的1变成2,又因为格子已经有两条边了,所以更新之后x和y对应的位置为0。
7、x = 2, y = 1,x与其前面第一个1配对,y与后面第一个2配对,更新后state中x = 0, y = 0。
8、x = 1, y = 2,x是某个路径的左半边,y是某个路径的右半边,又因为x和y在轮廓线中是相邻的,所以x和y是属于同一个路径的,这种情况只会发生在最后一个合法的格子。
接下来分析数据,在f[i, j, s]中s是轮廓线的状态,因为我们是用四进制来表示三进制,而4的13次方是等于67108864,而有效的状态只有4w多个,所以插头dp在存状态的时候一般是用哈希表来存的,而且哈希表最好不要用stl中的哈希表,因为插头dp的常数比较大,题目卡得比较严,所以现在我们要手写哈希表…手写哈希表的方法:
1、开放寻址法
2、拉链法
哈希表的作用:从较庞大的空间/值域,把它映射到一个较小的空间(0 ~ N)。
结合这道题来介绍手写哈希表的两种做法:
当要存储的数是x时,我们可以构造一个哈希函数h(x),这个函数它可以把-109 ~ 109的一个数映射到0 ~ 105之间的一个数,通常会采取x % 105的做法,值域比较大,但是映射的结果比较小,所以必然会产生冲突,也就是我们可能会把两个相同的数映射成同一个数,对于冲突的解决方式可以采用两种方法(开放寻址法/拉链法)。
拉链法:
先开一个长度为105的数组,当两个数发生冲突的时候,就在某个位置i拉下一条链,把之前的数放在链的第一个位置,然后把新得到的数放在i位置,类似于对于某一个数组元素接一个邻接表。哈希算法是一种期望算法,虽然说每一个位置都有可能拉下来一条链,但是在平均情况下,每一条链的长度可以看成是常数,所以哈希表的时间复杂度可以看成O(1)。
我们在建立一个哈希表的长度的时候一般取成一个质数(就是取模的数),而且这个质数要离2的n次方尽可能远。定义h[N]哈希数组,对于每一个“槽”,我们要向下拉一条链(类似于之前的链表),链表要存两个东西,一个是它的值e[idx],另一个是下一个值的下标ne[idx],具体做法和对链表的插入查找相同。拉链法的代码如下:
const int N = 100003; int h[N], e[N], ne[N], idx; int insert(int x){ int k = (x % N + N) % N; e[idx] = x; ne[idx] = h[k]; h[k] = idx++; } int find(int x){ int k = (x % N + N) % N; for(int i = h[k]; i != -1; i = ne[i]){ if(e[i] == x) return 1; } return 0; } int main(){ int n, m; cin >> n; char p[2]; memset(h, -1, sizeof(h)); while(n--){ scanf("%s%d", p, &m); if(p[0] == 'I') insert(m); else{ if(find(m)) cout << "Yes\n"; else cout << "No\n"; } } return 0; }
开放寻址法:
它只开了一个一维数组,一维数组的长度一般要开到题目数据范围的两到三倍(这道题开到20w ~ 30w),这样的话冲突的概率就小一点。开放寻址法就像我们去厕所找坑位,我想要的坑位有人了,就按顺序看看下一个空位有没有人,以此类推,直到找到坑位为止。开放寻址法的代码如下:
const int N = 200003, null = 0x3f3f3f3f; int find(int x){ int k = (x % N + N) % N; while(h[k] != null && h[k] != x){ k++; if(k == N) k = 0; } return k; } int main(){ int n, m; cin >> n; char p[2]; memset(h, 0x3f, sizeof(h)); while(n--){ scanf("%s%d", p, &m); if(p[0] == 'I') h[find(m)] = m; else{ if(h[find(m)] == null) cout << "No\n"; else cout << "Yes\n"; } } return 0; }
言归正传,我在插头dp这道题用开放寻址法,另外,这个题目合法状态大约4w多个,估算一下5w * 144(格子数),大概是700多w个状态,有些题目的数量可能更多,所以要用到滚动数组。由于对于每个格子,总共的状态有6k多w个,合法状态只有不到5w个,我们去枚举的时候就没必要去枚举所有状态,而要用一个数组先存储每一次滚动的有效状态。估算下时间复杂度:f[i, j, s]假设所有有效状态数量是S(最多不到5w),再乘以i、j(n2),然后再算状态的时候,对于5和6的情况,我们是需要枚举找出与某条边配对的边,最坏情况下是需要O(N)的计算量,所以整个算法的时间复杂度就是S * n3,大概是5w * 12 * 12 * 12 = 8.64 * 107,但本质上来说没有这么高(有效状态不到5w,也不是所有状态都要枚举8种情况),这就是插头dp的具体思路。
接下来是这道题的代码实现:
(具体有点复杂,为了大家方便理解,我每一行我都加了注释,虽然我自己都觉得有点恶心…)
#include <iostream> #include <cstdio> #include <algorithm> #include <cmath> #include <string> #include <cstring> #include <map> #include <queue> using namespace std; typedef long long LL; void debug_out(){ cerr << endl; } template<typename Head, typename... Tail> void debug_out(Head H, Tail... T){ cerr << " " << to_string(H); debug_out(T...); } #ifdef local #define debug(...) cerr<<"["<<#__VA_ARGS__<<"]:",debug_out(__VA_ARGS__) #else #define debug(...) 55 #endif using namespace std; const int N = 50005, M = N * 2 + 7; //状态数量,3^13 ~ 6000万个,有效的大概为4万~5万个 //开放寻址法的数组通常是2~3倍,同时取成质数,用于取模 int g[15][15], q[2][N], cnt[2], h[2][M], ex, ey; //g是判断是不是障碍物 //q是滚动数组,存储的是某个有效状态对应在哈希表的下标 //h是滚动数组,滚动hash表,第二维是哈希值的位置,存储的是哈希表某个下标对应的具体有效状态(哈希值) //cnt数组是每一次滚动过程中(当前格子)有效状态的数量 LL v[2][M], ans; //v是有效状态对应的方案数,ans累加所有方案数 int set(int k, int v){ //构造四进制的第k位数字为v的数字 return v * (1 << k * 2); } int get(int state, int k){ //求第k个格子的状态,四进制的第k位数字 return state >> (k * 2) & 3; } int find(int cur, int x){ //开放寻址法找到给有效状态存储的哈希表下标 int t = x % M; //取模找到预定存储的位置 while(h[cur][t] != -1 && h[cur][t] != x){ //直到找到空位置或者发现已经存过了 if(++t == M) t = 0; //在按顺序寻找空位置的过程中,要是到了数组的右边界,就回到数组的头部再找 } return t; //返回有效状态存储的哈希表下标 } int insert(int cur, int state, LL w){ //在滚动哈希表中新加入有效状态 int t = find(cur, state); //给有效状态找存储下标 if(h[cur][t] == -1){ //这个有效状态之前没存过 q[cur][++cnt[cur]] = t; //储存它的下标 cnt更新当前格子的有效状态数 h[cur][t] = state; //储存具体的有效状态 v[cur][t] = w; //储存符合当前有效状态的所有方案数 } else v[cur][t] += w; //这个有效状态之前存过,把它的合法方案数累加 } int main(){ // ios::sync_with_stdio(false); // cin.tie(0), cout.tie(0); int n, m; cin >> n >> m; for(int i = 1; i <= n; i++){ //读入n * m的矩阵 char a[15]; scanf("%s", a + 1); for(int j = 1; j <= m; j++){ if(a[j] == '.'){ g[i][j] = 1; //不是障碍标为1,是障碍标为0 ex = i, ey = j; //记录最后一个有效格子,我们要在最后一个有效格子记录所有方案 } } } memset(h, -1, sizeof(h)); //初始化滚动哈希表("两个"哈希表的元素值均为-1) int cur = 0; insert(cur, 0, 1); //最初的分界线,对应的方案数为1 for(int i = 1; i <= n; i++){ //枚举所有行 for(int j = 1; j <= cnt[cur]; j++){ //更新下一行新的分界线状态,从轮廓线是 一条直线和上方最右边格子的最右边 转换到 一条直线和下方最左边格子的最左边 h[cur][q[cur][j]] <<= 2; //新的一行所有有效状态都整体右移一位(用<<的原因是所有有效状态是从右往左记录的) } for(int j = 1; j <= m; j++){ //枚举所有格子 int l = cur; //保存之前的状态(h[l][q[l][k]]是之前格子转移后的有效状态,v[l][q[l][k]]是之前格子转移后的方案数) cur ^= 1; //cur ^= 1,更新为当前格子 cnt[cur] = 0; //当前格子转移后的有效状态数量初始化为0 memset(h[cur], -1, sizeof(h[cur])); //清空滚动哈希表中记录当前的有效状态 for(int k = 1; k <= cnt[l]; k++){ //遍历从上一个格子转移之后得到的所有有效状态 int state = h[l][q[l][k]]; //state是具体的有效状态,便于后续对状态中某一特定位上的数进行修改 LL w = v[l][q[l][k]]; //w是符合这个有效状态的所有方案数 int x = get(state, j - 1), y = get(state, j); //x和y的具体位置跟之前图示的x和y相同 //下面是上面图示的所有情况 if(g[i][j] == 0){ //第一种情况 if(!x && !y){ insert(cur, state, w); } } else if(!x && !y){ //第二种情况 if(g[i + 1][j] && g[i][j + 1]) insert(cur, state + set(j - 1, 1) + set(j, 2), w); } else if(!x && y){ //第三种情况 if(g[i + 1][j]) insert(cur, state + set(j - 1, y) - set(j, y), w); if(g[i][j + 1]) insert(cur, state, w); } else if(x && !y){ //第四种情况 if(g[i][j + 1]) insert(cur, state + set(j, x) - set(j - 1, x), w); if(g[i + 1][j]) insert(cur, state, w); } else if(x == 1 && y == 1){ //第五种情况 for(int s = 1, u = j + 1;;u++){ int p = get(state, u); if(p == 1) s++; else if(p == 2){ //找到匹配的右括号 if(--s == 0){ insert(cur, state - set(j - 1, 1) - set(j, 1) - set(u, 1), w); break; } } } } else if(x == 2 && y == 2){ //第六种情况 for(int s = 1, u = j - 2;; u--){ int p = get(state, u); if(p == 2) s++; else if(p == 1){ //找到匹配的左括号 if(--s == 0){ insert(cur, state - set(j - 1, 2) - set(j, 2) + set(u, 1), w); break; } } } } else if(x == 2 && y == 1){ //第七种情况 insert(cur, state - set(j - 1, 2) - set(j, 1), w); } else if(i == ex && j == ey){ //第八种情况(已经到了最后一个非障碍格子) ans += w; //累加所有合法方案数 } } } } cout << ans << '\n'; return 0; }
P3190 [HNOI2007]神奇游乐园
这道题相当于一个n * m的棋盘,然后从里边选择一个回路,但这道题跟上一题不一样的地方是不一定每一个格子都要经过,回路里边包含的格子数量不能少于四,也就是起码要存在一个拐点。要我们求在所有的回路里权值和最大是多少,状态表示和上面那道题是类似的,只有状态转移不太一样,我们用f[i, j, S]遍历到当前第i行j列的格子轮廓线的状态是S时所有方案的集合,S在存插头状态的时候,跟上面那道题是类似的,也是用三进制(类似于括号序列的方式)来存下每条边的状态,主要是维护下所有插头的连通性。
状态转移是7种情况(上一道题格子可能是障碍物),我就不画图了,用文字说明(每个变量表示的东西都跟上一道题一样):
情况一:x = 0, y = 0, 这个格子有两种可能(因为这个格子可以走,可以不走),不走的话,insert(cur, state, w);;走的话,insert(cur, state + set(j - 1, 1) + set(j, 2), w + g[i][j]);
情况二:x = 0, y非0,经过这个格子的时候如果向右走,insert(cur, state, w + g[i][j]);
如果向下走,insert(cur, state + set(j - 1, y) - set(j, y), w + g[i][j]);
情况三:x非0, y = 0,经过这个格子的时候如果向右走,insert(cur, state + set(j, x) - set(j - 1, x), w + g[i][j]);如果向下走,insert(cur, state, w + g[i][j]);
情况四:如果x = 1, y = 1,在y的右边找到第一个2与y配对,把其更新为1,insert(cur, state -set(j - 1, 1) - set(j, 1) - set(u, 1), w + g[i][j]);
情况五:如果x = 2, y = 2,在x的左边找到第一个1与x配对,把其更新为2,insert(cur, state - set(j - 1, 2) - set(j, 2) + set(u, 1), w + g[i][j]);
情况六:x = 2, y = 1,这种状态其它边不受影响,直接转移就好了insert(cur, state - set(j - 1, 2) - set(j, 1), w + g[i][j]);
情况七:x = 1, y = 2,这种状态说明轮廓线的上方已经形成了回路,因为这道题不是所有的格子都要走,所以当遇到这种情况的时候,我们要更新权值和的最大值:ans = max(ans, w + g[i][j]);具体的代码实现如下:
(跟第一道题很像,只是状态转移的条件和过程不一样,其他辅助函数都一样)
#include <iostream> #include <cstdio> #include <algorithm> #include <cmath> #include <string> #include <cstring> #include <map> #include <queue> using namespace std; typedef long long LL; void debug_out(){ cerr << endl; } template<typename Head, typename... Tail> void debug_out(Head H, Tail... T){ cerr << " " << to_string(H); debug_out(T...); } #ifdef local #define debug(...) cerr<<"["<<#__VA_ARGS__<<"]:",debug_out(__VA_ARGS__) #else #define debug(...) 55 #endif using namespace std; const int N = 130, M = N * 2 + 7; int g[N][N], h[2][M], q[2][N], cnt[2]; LL v[2][M], ans = -1e9; int set(int k, int v){ return v * (1 << k * 2); } int get(int state, int k){ return state >> k * 2 & 3; } int find(int cur, LL x){ int t = x % M; while(h[cur][t] != -1 && h[cur][t] != x){ if(++t == M) t = 0; } return t; } int insert(int cur, int x, LL w){ int t = find(cur, x); if(h[cur][t] == -1){ q[cur][++cnt[cur]] = t; h[cur][t] = x; v[cur][t] = w; } else v[cur][t] = max(v[cur][t], w); } int main(){ // ios::sync_with_stdio(false); // cin.tie(0), cout.tie(0); int n, m; cin >> n >> m; for(int i = 1; i <= n; i++){ for(int j = 1; j <= m; j++){ cin >> g[i][j]; } } memset(h, -1, sizeof h); int cur = 0; insert(cur, 0, 0); for(int i = 1; i <= n; i++){ for(int j = 1; j <= cnt[cur]; j++){ h[cur][q[cur][j]] <<= 2; } for(int j = 1; j <= m; j++){ int l = cur; cur ^= 1; cnt[cur] = 0; memset(h[cur], -1, sizeof(h[cur])); for(int k = 1; k <= cnt[l]; k++){ int state = h[l][q[l][k]]; LL w = v[l][q[l][k]]; int x = get(state, j - 1), y = get(state, j); if(!x && !y){ if(i < n && j < m) insert(cur, state + set(j - 1, 1) + set(j, 2), w + g[i][j]); insert(cur, state, w); } else if(!x && y){ if(i < n) insert(cur, state + set(j - 1, y) - set(j, y), w + g[i][j]); if(j < m) insert(cur, state, w + g[i][j]); } else if(x && !y){ if(i < n) insert(cur, state, w + g[i][j]); if(j < m) insert(cur, state + set(j, x) - set(j - 1, x), w + g[i][j]); } else if(x == 1 && y == 1){ for(int u = j + 1, s = 1;; u++){ int p = get(state, u); if(p == 1) s++; else if(p == 2){ if(--s == 0){ insert(cur, state -set(j - 1, 1) - set(j, 1) - set(u, 1), w + g[i][j]); break; } } } } else if(x == 2 && y == 2){ for(int u = j - 2, s = 1;; u--){ int p = get(state, u); if(p == 2) s++; else if(p == 1){ if(--s == 0){ insert(cur, state - set(j - 1, 2) - set(j, 2) + set(u, 1), w + g[i][j]); break; } } } } else if(x == 2 && y == 1){ insert(cur, state - set(j - 1, 2) - set(j, 1), w + g[i][j]); } else ans = max(ans, w + g[i][j]); } } } cout << ans << '\n'; return 0; }
P3272 [SCOI2011]地板
这道题是一个非回路的问题,在r * c的地面上铺地板,地面上可能有障碍物,没有障碍物的地方一定要铺上地板,而且铺的地板要呈”L”型(如题目图示),求铺满整个地面的总方案数。题目中r和c没有大小关系,但规定了r * c <= 100,因此r和c的最小值一定是小于等于10,从数据范围上看它也是可以用插头dp的,这一题跟上两道题不一样,它不是一个回路,就不可以用类似括号序列的方式来表示轮廓线的状态,这道题依旧用f[i, j, S]来表示遍历到第i行第j列的格子,轮廓线的状态是S时的方案数。这道题轮廓线上的插头状态
存的是”L”型地板经过轮廓线上的某一条边时,在轮廓线上方是否已经“拐弯”,它存的是每个插头当前有没有“拐弯”,如果无插头,记录为0;如果有插头且还没“拐弯”,记录为1;如果有插头且已经“拐弯”,记录为2。重点是如何进行状态转移,可以分成7种情况((每个变量表示的东西都跟上一道题一样):
情况一:如果这个格子是障碍物,insert(cur, state, w);
情况二:当格子不是障碍物时(下面的情况都是格子不是障碍物的情况),x = 0, y = 0,还可以分成三种子情况,以当前格子为起点,如果只往下走,insert(cur, state + set(j - 1, 1), w);如果只往右走,insert(cur, state + set(j, 1), w);如果既往下又往右走,insert(cur, state + set(j - 1, 2) + set(j, 2), w);
情况三:x = 0, y = 1,如果往下走,insert(cur, state + set(j - 1, 1) - set(j, 1), w);如果往右走insert(cur, state + set(j, 1), w);
情况四:x = 0, y = 2,如果往下走,insert(cur, state - set(j, 2) + set(j - 1, 2), w);如果在当前格子停下insert(cur, state - set(j, 2), w);如果已经遍历到最后一个有效格子,更新方案数,ans = (ans + w) % mod;
情况五:x = 1, y = 0,如果往右走,insert(cur, state - set(j - 1, 1) + set(j , 1) ,w);如果往下走,insert(cur, state + set(j - 1, 1), w);
情况六:x = 2, y = 0,如果往右走,insert(cur, state - set(j - 1, 2) + set(j , 2), w);如果在当前格子停下insert(cur, state - set(j - 1, 2), w);如果已经遍历到最后一个有效格子,更新方案数,ans = (ans + w) % mod;
情况七:x = 1, y = 1,这种情况说明这个格子是某个“L”型地板的“拐弯”处,insert(cur, state - set(j - 1, 1) - set(j, 1), w);如果此时已经遍历到了最后一个有效的格子,更新方案数,ans = (ans + w) % mod;
注意,这道题在进行状态转移的时候要考虑当前“L”型地板覆盖的地方有没有障碍物。具体的代码实现如下:
(跟前两道插头dp很像,只是状态转移的条件和过程不一样,其他辅助函数都一样)
#include <iostream> #include <cstdio> #include <algorithm> #include <cmath> #include <string> #include <cstring> #include <map> #include <queue> using namespace std; typedef long long LL; void debug_out(){ cerr << endl; } template<typename Head, typename... Tail> void debug_out(Head H, Tail... T){ cerr << " " << to_string(H); debug_out(T...); } #ifdef local #define debug(...) cerr<<"["<<#__VA_ARGS__<<"]:",debug_out(__VA_ARGS__) #else #define debug(...) 55 #endif const int N = 180000, M = N * 2 + 7, mod = 20110520; int ex, ey, h[2][M], q[2][N], v[2][M], ans, cnt[2], g[105][105]; int set(int k, int v){ return v * (1 << k * 2); } int get(int state, int k){ return state >> k * 2 & 3; } int find(int cur, int x){ int t = x % M; while(h[cur][t] != -1 && h[cur][t] != x){ if(++t == M) t = 0; } return t; } int insert(int cur, int state, int w){ int t = find(cur, state); if(h[cur][t] == -1){ q[cur][++cnt[cur]] = t; h[cur][t] = state; v[cur][t] = w; } else v[cur][t] = (v[cur][t] + w) % mod; return 0; } int main(){ // ios::sync_with_stdio(false); // cin.tie(0), cout.tie(0); int n, m; char a[105]; cin >> n >> m; for(int i = 1; i <= n; i++){ scanf("%s", a + 1); for(int j = 1; j <= m; j++){ if(a[j] == '_'){ g[i][j] = 1; ex = i, ey = j; } } } if(n < m){ swap(n, m), swap(ex, ey); for(int i = 1; i <= n; i++){ for(int j = 1; j < i; j++){ swap(g[i][j], g[j][i]); } } } memset(h, -1, sizeof(h)); int cur = 0; insert(cur, 0, 1); for(int i = 1; i <= n; i++){ for(int j = 1; j <= cnt[cur]; j++){ h[cur][q[cur][j]] <<= 2; } for(int j = 1; j <= m; j++){ int l = cur; cur ^= 1, cnt[cur] = 0; memset(h[cur], -1, sizeof h[cur]); for(int k = 1; k <= cnt[l]; k++){ int state = h[l][q[l][k]], w = v[l][q[l][k]]; int x = get(state, j - 1), y = get(state, j); if(!g[i][j]){ if(!x && !y) insert(cur, state, w); } else if(!x && !y){ if(g[i][j + 1]) insert(cur, state + set(j, 1), w); if(g[i + 1][j]) insert(cur, state + set(j - 1, 1), w); if(g[i][j + 1] && g[i + 1][j]) insert(cur, state + set(j - 1, 2) + set(j, 2), w); } else if(!x && y == 1){ if(g[i][j + 1]) insert(cur, state + set(j, 1), w); if(g[i + 1][j]) insert(cur, state + set(j - 1, 1) - set(j, 1), w); } else if(!x && y == 2){ if(i == ex && j == ey) ans = (ans + w) % mod; else if(g[i + 1][j]) insert(cur, state - set(j, 2) + set(j - 1, 2), w); insert(cur, state - set(j, 2), w); } else if(x == 1 && !y){ if(g[i][j + 1]) insert(cur, state - set(j - 1, 1) + set(j , 1) ,w); if(g[i + 1][j]) insert(cur, state + set(j - 1, 1), w); } else if(x == 2 && !y){ if(i == ex && j == ey) ans = (ans + w) % mod; else if(g[i][j + 1]) insert(cur, state - set(j - 1, 2) + set(j , 2), w); insert(cur, state - set(j - 1, 2), w); } else if(x == 1 && y == 1){ if(i == ex && j == ey) ans = (ans + w) % mod; insert(cur, state - set(j - 1, 1) - set(j, 1), w); } } } } cout << ans << '\n'; return 0; }
期望DP
在介绍期望dp之前,先做一道简单的数学求期望,熟悉一下算法题是怎样考查期望的。
UVA12230 过河 Crossing Rivers
题意:从A到B需要经过n条河,已知AB间距离D和每条河的长度L以及在该条河上的船速v,求A到B平均情况下需多长时间。
陆地行走速度为1,船的位置和朝向均匀随机。因为在某条河里面船的位置和朝向是均匀随机的,人在河边最久等待2 * l / v(人到河边,船刚走),最理想情况是不用等待,所以平均等待时间的期望就是l / v,加上人坐船过河需要时间,所以人过河(包括等船)需要时间的期望为2 * l / v,一直人在陆地上的速度为1,所以每遇到河时,需要的期望时间就是在总路程长度中,减去河的长度(- l),再加上人过这条河需要时间的期望(+ 2 * l / v)。具体的代码实现如下:
#include <bits/stdc++.h> using namespace std; typedef long long LL; int main(){ ios::sync_with_stdio(false); cin.tie(0), cout.tie(0); int n, s = 1; double d, p, l, v; while(cin >> n >> d){ if(n == 0 && d == 0) break; while(n--){ cin >> p >> l >> v; d = d - l + 2 * l / v; debug(n, d); } printf("Case %d: %.3lf\n\n", s++, d); } return 0; }
期望dp / 概率dp的概念:
根据概率分析,递推求出每个状态的期望的算法。
期望DP / 概率DP常见的状态表示及其转移:
1、设成dp[i]表示已经完成i个,要达到目标状态的期望。也就是由i状态变成目标状态的期望。对于这种方法,转移的时候要选择刷表法倒序枚举。(根据这个状态本身就可以理解)
2、设成dp[i]表示已经完成i个的期望。对于这种方法,转移的时候要选择填表法正序枚举。
对于以上两种方法,很多时候可以互换。但是有些时候不能互换。需要经过具体情况灵活判断。
3、设成dp[i][j]表示i种物品选择了j个的期望。
4、设成dp[i][j]表示有i个第一种物品,j个第二种物品的期望。
对于以上两种方法,就是二维的状态转移。
然后就是转移的具体过程。对于状态转移,一般我们要把整个过程拆解成两种情况:已处理和未处理,也就是符合需要和不符合需要。比如抛硬币,要算正面朝上的期望,那么就把抛硬币的过程拆成:朝上和不朝上。或者掷一个有N面的骰子,要算掷多少次才能都掷完各面的期望,那么就把这个掷骰子的过程拆成:掷到已经处理的面和掷到未处理的面。
这样的话,就可以通过两种过程的概率以及上面所讲述的期望的性质进行转移。
对于填表、刷表法的选择:一般来讲,初始状态确定时用顺推填表,终止状态确定时可用逆推刷表。SP1026 FAVDICE - Favorite Dice
一个n面的骰子,求期望掷几次能使得每一面都被掷到。dp[i]表示已经从n个面中掷出来i面后,掷出所有面的次数期望,所以dp[n] = 0, dp[0]即为所求。我们可以采用逆推刷表,已知在n面的骰子中已经掷出了i面,再掷一次恰好是没掷出的面的概率为(n - i) / n,所以从n面的骰子中掷出之前没掷出的面的期望次数是n / (n - i),因为是逆推刷表,所以状态转移方程:dp[i] = dp[i + 1] + n * 1.0 / (n - i); dp[0]即为所求的期望次数。具体的代码实现如下:
#include <iostream> #include <cstdio> #include <algorithm> #include <cmath> #include <string> #include <cstring> #include <map> #include <queue> using namespace std; typedef long long LL; double dp[1005]; int main(){ ios::sync_with_stdio(false); cin.tie(0), cout.tie(0); int n, t, s = 1; cin >> t; while(t--){ cin >> n; dp[n] = 0; for(int i = n - 1; i >= 0; i--){ dp[i] = dp[i + 1] + n * 1.0 / (n - i); } printf("%.2lf\n", dp[0]); } return 0; }
【SGU495】【Kids and Prizes】
这道题是我在网上找的期望dp的基础题,做完后想提交,才发现SGU这个oj没了…
题意:有n个奖品放在n个盒子里,有m个小朋友轮流去选择一个盒子,若有奖品则拿走,无论有没有奖品都要将空盒子放回去。问最后获得奖品个数的期望。
求获得奖品个数的期望,只要把每一个小朋友拿到奖品的概率相加即为所求,所以我们要dp求每一轮小朋友拿到奖品的概率,第一个小朋友拿到奖品的概率为1,dp[1] = 1;之后第i个小朋友拿到奖品的概率(dp[i])与第i - 1个小朋友拿到奖品(dp[i - 1])的概率有关,分为两种情况:当第i - 1个小朋友没有拿到奖品时,此时第i个小朋友拿到奖品的概率与第i - 1个小朋友拿到奖品的概率相同,此时dp[i] = (1 - dp[i - 1]) * dp[i -1];当第i - 1个小朋友拿到奖品时,第i个小朋友拿到奖品的概率是(dp[i - 1] - 1.0 / n),此时dp[i] = dp[i - 1] * (dp[i - 1] - 1.0 / n),结合起来,状态转移方程:dp[i] = (1 - dp[i - 1]) * dp[i - 1] + dp[i - 1] * (dp[i - 1] - 1 / n)。具体的代码实现如下:
#include <bits/stdc++.h> using namespace std; int n,m; double dp[100005], ans; int main(){ ios::sync_with_stdio(false); cin.tie(0), cout.tie(0); while(~scanf("%d %d",&n,&m)){ dp[1] = 1.0; for(int i = 2; i <= m; i++){ dp[i] = (1 - dp[i - 1]) * dp[i - 1] + dp[i - 1] * (dp[i - 1] - 1.0 / n); } for(int i = 1; i <= m; i++){ ans += dp[i]; } printf("%.10lf\n", ans); } return 0; }
CF148D Bag of mice
cf的英文题,我大概说下题意:袋子里有 w 只白鼠和 b 只黑鼠,公主和龙轮流从袋子里抓老鼠。谁先抓到白色老鼠谁就赢,如果袋子里没有老鼠了并且没有谁抓到白色老鼠,那么算龙赢。公主每次抓一只老鼠,龙每次抓完一只老鼠之后会有一只老鼠跑出来。每次抓的老鼠和跑出来的老鼠都是随机的。公主先抓。问公主赢的概率。
设f[i, j]为轮到公主时袋子里有i只白鼠,j只黑鼠,公主赢的概率。初始化边界,f[0,j] = 0因为没有白鼠了算龙赢,f[i, 0] = 1因为抓一只就是白鼠,公主赢。考虑f[i, j]的转移(每一轮公主和龙轮流拿,可以分成四种情况):
情况一:公主抓到了一只白鼠,公主赢了(龙不用抓了),这种情况发生的概率为:i / (i + j)。
情况二:公主抓到了一只黑鼠,龙抓到了一只白鼠(龙胜利了),这种情况发生的概率为:j / (i + j) * i / (i + j -1)。
情况三:公主抓到了一只黑鼠,龙抓到了一只黑鼠,跑出来了一只白鼠,转移到了f[i - 1, j - 2],这种情况发生的概率:j / (i + j) * (j - 1) / (i + j - 1) * i / (i + j - 2)。
情况四:公主抓到了一只黑鼠,龙抓到了一只黑鼠,跑出来了一只黑鼠,转移到了f[i, j - 3],这种情况发生的概率:j / (i + j) * (j - 1) / (i + j - 1) * (j - 2) / (i + j - 2)。
考虑公主赢的概率,第二种情况不参与计算。并且要保证后两种情况合法,所以还要判断i, j的大小,满足第三种情况至少要有 3 只黑鼠,满足第四种情况要有 1 只白鼠和 2 只黑鼠。具体的代码实现如下:
#include <bits/stdc++.h> using namespace std; typedef long long LL; void debug_out(){ cerr << endl; } template<typename Head, typename... Tail> void debug_out(Head H, Tail... T){ cerr << " " << to_string(H); debug_out(T...); } #ifdef local #define debug(...) cerr<<"["<<#__VA_ARGS__<<"]:",debug_out(__VA_ARGS__) #else #define debug(...) 55 #endif double dp[1005][1005]; int main(){ ios::sync_with_stdio(false); cin.tie(0), cout.tie(0); int w, b; cin >> w >> b; //dp[w][b] for(int i = 1; i <= w; i++) dp[i][0] = 1; for(int j = 1; j <= b; j++) dp[0][j] = 0; for(int i = 1; i <= w; i++){ for(int j = 1; j <= b; j++){ dp[i][j] += (double)i / (i + j); //公主一次就拿到了白鼠 if(j >= 3) dp[i][j] += dp[i][j - 3] * (double)j / (i + j) * (double)(j - 1) / (i + j - 1) * (double)(j - 2) / (i + j - 2); //公主和龙拿的都是黑鼠,跑出来的是黑鼠 if(i >= 1 && j >= 2) dp[i][j] += dp[i - 1][j - 2] * (double)j / (i + j) * (double)(j - 1) / (i + j - 1) * (double)i / (i + j - 2); //公主拿的是黑鼠,龙拿的是黑鼠,跑出来的是白鼠 } } printf("%.9lf", dp[w][b]); return 0; }
POJ 3071 Football
先说说这道题的题意:有2n次方个队,已知任意两个队之间每个队获胜的概率,比赛的规则是相邻的两个队伍之间比赛,赢的继续下一轮,输的直接淘汰(相邻的两个队伍是指,1和2,3和4,5和6…如果1和2中假设1赢了,1再跟3和4中的赢家比赛,这样最后赢的那个队一共打了n场比赛。题目的输入是一个2 n的矩阵,第i行第j列的小数表示第i队战胜第j队的概率,所以p[i][j] + p[j][i] == 1。要我们通过概率求得哪一支队伍最终取得冠军的概率最大。
我们用dp[i][j]表示j参加的第i场比赛赢的概率,那么有递推方程dp[i] [j] = dp[i - 1][j] * dp[ i - 1][k] * p[j][k],j能参加的第i场比赛,那么j参加的第i - 1场肯定赢,所以此时有dp[i - 1][j],第i场比赛j的对手是k,k能参加第i场比赛,那么k参加的第i - 1场比赛也肯定赢,所以此时有dp[i - 1][k],因为我们是假设第i场比赛i战胜j,所以有p[j][k]。
这道题的关键是判断第i轮,哪两支队可能进行比赛,因为每场比赛只允许相邻两支上一轮获胜的队伍比赛。这需要用到位运算,我们把1 ~ 2n支队伍的编号变成0 ~ 2n - 1,再把每支队伍的编号看成是二进制(第5支队伍的编号为:101),假设n = 3, 所以第一轮比赛的队伍:000 vs 001,010 vs 011,100 vs 101,110 vs 111。我们发现两两比赛的队伍的编号只有最后一位是不同的;假设第一轮获胜的队伍是第1支(编号为0,二进制:000),第4支(编号为3,二进制:011),第6支(编号为5,101),第7支(编号为6,110),所以此时第二轮比赛:000 vs 011,101 vs 110,这时我们又发现这一轮两两比赛的队伍的编号只要倒数第二位是不同的,以此类推…最终我发现了规律:第i轮比赛能进行比赛的队伍j和k需满足:(((j - 1) >> (i - 1)) ^ 1) == ((k - 1) >> (i - 1)),j - 1和k - 1的含义相当于我们上面第i支队伍的编号为i - 1,当进行到第i轮的时候,我们判断的是编号的倒数第i位(编号右移i - 1,看最后一位(与1异或之后)是否与其他队伍的编号相同),这一系列的操作就是为了判断两支队伍的编号的二进制是不是除了倒数第i位(倒数第i位之后的数不管)之外,前面的都一样,若满足条件,这两支队伍在第i轮就有可能进行比赛。
最后遍历dp[n][i],找到最大的概率,记录并输出dp[n][i]中的i即可。具体的代码实现如下:
#include <iostream> #include <cstdio> #include <algorithm> #include <cmath> #include <string> #include <cstring> #include <map> #include <queue> using namespace std; typedef long long LL; double dp[130][130], p[130][130], maxx; int main(){ ios::sync_with_stdio(false); cin.tie(0), cout.tie(0); int n; while(cin >> n){ if(n == -1) break; memset(dp, 0, sizeof dp); int len = 1 << n, s; for(int i = 1; i <= len; i++){ for(int j = 1; j <= len; j++){ cin >> p[i][j]; } } for(int i = 1; i <= len; i++) dp[0][i] = 1; for(int i = 1; i <= n; i++){ for(int j = 1; j <= len; j++){ for(int k = 1; k <= len; k++){ if((((j - 1) >> (i - 1)) ^ 1) == ((k - 1) >> (i - 1))) dp[i][j] += dp[i - 1][j] * dp[i - 1][k] * p[j][k]; } } } maxx = 0; for(int i = 1; i <= len; i++){ if(dp[n][i] > maxx){ maxx = dp[n][i]; s = i; } } cout << s << endl; } return 0; }
CodeForces 768 D - Jon and Orbs
题目大意:有k种物品,每天只能取一种物品,取后放回,有q组询问,每次给出一个数pi,求取物品的期望天数n满足全取完k种物品的概率不小于pi / 2000。
我们用dp[i][j]表示第i天已经出现了j种物品的概率,状态转移方程:dp[i][j] = dp[i - 1][j] * j / k + dp[i - 1][j - 1] * (k - j + 1) / k;所以我们要开始从第一天开始遍历,终止条件是p <= 1000(题目给出了p1的范围),这道题相当于在动态转移的过程中打表了当1 <= p <= 1000时的所有情况。在特定的前i天对已经取得了j(1 ~ k)种物品进行递推求出概率,到最后求出来dp[i][k]之后进行while(p <= 1000 && dp[i][k] * 2000 > p) s[p++] = i; 把符合概率条件的p记录为i。具体的代码实现如下:
#include <bits/stdc++.h> using namespace std; typedef long long LL; void debug_out(){ cerr << endl; } template<typename Head, typename... Tail> void debug_out(Head H, Tail... T){ cerr << " " << to_string(H); debug_out(T...); } #ifdef local #define debug(...) cerr<<"["<<#__VA_ARGS__<<"]:",debug_out(__VA_ARGS__) #else #define debug(...) 55 #endif double dp[10005][1005]; LL s[1005]; int main(){ ios::sync_with_stdio(false); cin.tie(0), cout.tie(0); int n, k, q, p = 1; cin >> k >> q; dp[0][0] = 1; for(int i = 1; p <= 1000; i++){ for(int j = 1; j <= k; j++){ dp[i][j] = (dp[i - 1][j] * j + dp[i - 1][j - 1] * (k - j + 1)) / k; } while(p <= 1000 && dp[i][k] * 2000 > p){ s[p++] = i; } } while(q--){ cin >> n; cout << s[n] << endl; } return 0; }
POJ2096 Collecting Bugs
看英文看了半天的废话,这道题的大意就是:一个软件有s个子系统,会产生n种bug。某人一天发现一个bug,这个bug属于某种bug分类,也属于某个子系统。每个bug属于某个子系统的概率是1 / s,属于某种bug分类的概率是1 / n。求发现n种bug,且s个子系统都找到bug的期望天数。
这道题就属于期望dp中,终止状态确定时用逆推刷表。我们用dp[i][j]表示以及找到了i中bug分类,这些bug属于j个子系统时,达到目标状态的期望天数。我们这道题的目标是找到n中bug分类,s个子系统的bug。那么就有dp[i][j] = 0,因为此时已经达到了目标状态,不需要更多的天数去发现bug了,达到目标状态的期望天数自然就为0。于是就已目标状态为起点开始递推,答案是dp[i][j]。
dp[i][j]的状态转移情况:
1、dp[i][j],发现一个bug属于已经发现的i种bug分类,j个子系统,这情况发生的概率是:p1 = i / n * j / s
2、dp[i][j + 1],发现一个bug属于已经发现的i种bug分类,但不属于已经发现的j个子系统,这种情况发生的概率是:p2 = i / n * (s - j) / s
3、dp[i + 1][j],发现一个bug不属于已经发现的i中bug分类,属于已经发现的j个子系统,这种情况发生的概率是:p3 = (n - i) / i * j / s
4、dp[i + 1][j + 1],发现的一个bug既不属于已经发现的i个子系统,也不属于已经发现的j个子系统,这种情况发生的概率是:p4 = (n - i) / i * (s - j) / j
因为我们是从终止状态逆推到初始状态的,每一个状态到终止状态期望的天数,都是由它转移到若干状态的概率 与 其对应状态到终止状态期望天数的乘积 相累加得到的(因为是再找一个bug才能转移,所以还要加1),所以我们可以得到状态转移方程:dp[i][j] = p1 * dp[i][j] + p2 * dp[i][j + 1] + p3 * dp[i + 1][j] + p4 * dp[i + 1][j + 1] + 1,把等式两边的dp[i][j]合并可得最终的状态转移方程:dp[i][j] = (dp[i][j + 1] * i * (s - j) + dp[i + 1][j] * (n - i) * j + dp[i + 1][j + 1] * (n - i) * (s - j) + n * s) / (n * s - i * j);
最终得到的dp[0][0]即为发现n种bug,且s个子系统都找到bug的期望天数。具体的代码实现如下:
#include <iostream> #include <cstdio> #include <algorithm> #include <cmath> #include <string> #include <cstring> #include <map> #include <queue> using namespace std; double dp[1005][1005]; int main(){ ios::sync_with_stdio(false); cin.tie(0), cout.tie(0); int n, s; cin >> n >> s; for(int i = n; i >= 0; i--){ for(int j = s; j >= 0; j--){ if(n == i && s == j) continue; //因为是终止状态,初始化就为0,不用处理 dp[i][j] = (dp[i][j + 1] * i * (s - j) + dp[i + 1][j] * (n - i) * j + dp[i + 1][j + 1] * (n - i) * (s - j) + n * s) / (n * s - i * j); } } printf("%.4lf", dp[0][0]); return 0; }
P1850 [NOIP2016 提高组] 换教室
题目比较长,我先说说大概的意思:牛牛要上n个时间段的课,第i个时间段在ci号教室,可以申请换到di号教室,申请成功的概率为pi,至多可以申请m节课进行交换。第i个时间段的课上完后要走到第i + 1个时间段的教室,给出一张图v个教室e条路,移动会消耗体力,申请哪几门课程可以使他因在教室间移动耗费的体力值的总和的期望值最小,也就是求出最小的期望路程和。
对于这个无向连通图,先用Floyd求出最短路,为后续状态转移带来便利(我们用f[a][b]表示第a间教室到第b间教室之间的距离)。假设现在在第i - 1个时间段,考虑去第i个时间段上课,如果申请从ci号教室交换到第di号教室上课,则有pi的概率申请成功,1 - pi的概率申请不成功,而且每人只有m个申请的机会(无论申请成功与否,都看作用了申请的机会),求出到第n个时间段走过的最小期望路程和。我们定义dp[i][j][0]表示前i个时间段已经申请了j次,且第i个时间段不申请换教室;dp[i][j][1]表示前i个时间段已经申请了j次,且第i个时间段申请换教室。最终最小的期望路程和就是min{dp[n][j][0], dp[n][j][1]},j的取值范围是0 ~ m。注意初始化边界dp[1][0][0] = dp[1][1][1] = 0。
现在考虑dp[i][j][0/1]的状态转移:
一:dp[i][j][0],第i个时间段不换教室,此时的状态可能是第i - 1个时间段没申请换教室转移来的,也有可能是第i - 1个时间段申请换教室(有pi - 1概率申请成功)转移来的。前者为:dp[i - 1][j][0] + f[c[i - 1]][c[i]],对于后者的情况:如果申请成功,f[d[i - 1]][c[i]] * p[i - 1];如果申请失败,f[c[i - 1]][c[i]] * (1 - p[i - 1]),综合起来,后者为:dp[i - 1][j ][1] + f[d[i - 1]][c[i]] * p[i - 1] + f[c[i - 1]][c[i]] * (1 - p[i - 1])。取前者和后者路程期望的最小值,所以情况一的转移方程:dp[i][j][0] = min(dp[i - 1][j][0] + f[c[i - 1]][c[i]], (dp[i - 1][j][1] + f[d[i - 1]][c[i]] * p[i - 1] + f[c[i - 1]][c[i]] * (1 - p[i - 1])));
二:dp[i][j][1],第i个时间段申请换教室,此时的状态可能是第i - 1个时间段没申请换教室转移来的,也有可能是第i - 1个时间段申请换教室(有pi - 1概率申请成功)转移来的。前者:如果第i个时间段申请成功,f[c[i - 1]][d[i]] * p[i],如果第i个时间段申请不成功,f[c[i - 1][c[i]]] * (1 - p[i]),综合起来,前者:dp[i - 1][j - 1][0] + f[c[i - 1]][d[i]] * p[i] + f[c[i - 1]][c[i]] * (1 - p[i])。后者要分成四种情况(第i - 1和i个时间段都申请换教室了,都有申请成功和失败两种情况),如果都申请成功,f[d[i - 1]][d[i]] * p[i - 1] * p[i];如果都申请失败,f[c[i - 1]][c[i]] * (1 - p[i]) * (1 - p[i - 1]);如果第i - 1个时间段申请成功,第i个时间段申请失败,f[d[i - 1]][c[i]] * p[i - 1] * (1 - p[i]);如果第i - 1个时间段申请失败,第i个时间段申请成功,f[c[i - 1]][d[i]] * (1 - p[i - 1]) * p[i],综合四种情况起来,后者为:dp[i - 1][j - 1][1] + f[c[i - 1]][c[i]] * (1 - p[i]) * (1 - p[i - 1]) + f[c[i - 1]][d[i]] * (1 - p[i - 1]) * p[i] + f[d[i - 1]][c[i]] * p[i - 1] * (1 - p[i]) + f[d[i - 1]][d[i]] * p[i - 1] * p[i]。取前者和后者路程期望的最小值,所以情况二的转移方程:dp[i][j][1] = min(dp[i - 1][j - 1][0] + f[c[i - 1]][d[i]] * p[i] + f[c[i - 1]][c[i]] * (1 - p[i]), dp[i - 1][j - 1][1] + f[c[i - 1]][c[i]] * (1 - p[i]) * (1 - p[i - 1]) + f[c[i - 1]][d[i]] * (1 - p[i - 1]) * p[i] + f[d[i - 1]][c[i]] * p[i - 1] * (1 - p[i]) + f[d[i - 1]][d[i]] * p[i - 1] * p[i]);
最后,取dp[n][j][0/1]的最小值(j的范围:1 ~ m)即为最终的答案。具体的代码实现如下:
#include <bits/stdc++.h> using namespace std; typedef long long LL; void debug_out(){ cerr << endl; } template<typename Head, typename... Tail> void debug_out(Head H, Tail... T){ cerr << " " << to_string(H); debug_out(T...); } #ifdef local #define debug(...) cerr<<"["<<#__VA_ARGS__<<"]:",debug_out(__VA_ARGS__) #else #define debug(...) 55 #endif double dp[2005][2005][2], p[2005], s = 1e9; int c[2005], d[2005], f[2005][2005]; int main(){ ios::sync_with_stdio(false); cin.tie(0), cout.tie(0); int n, m, v, e, a, b, w; cin >> n >> m >> v >> e; for(int i = 1; i <= n; i++) cin >> c[i]; for(int i = 1; i <= n; i++) cin >> d[i]; for(int i = 1; i <= n; i++) cin >> p[i]; for(int i = 1; i <= v; i++){ for(int j = 1; j < i; j++){ f[i][j] = f[j][i] = 1e9; } } for(int i = 1; i <= e; i++){ cin >> a >> b >> w; f[a][b] = f[b][a] = min(w, f[a][b]); } for(int k = 1; k <= v; k++){ for(int i = 1; i <= v; i++){ for(int j = 1; j < i; j++){ if(f[i][j] > f[i][k] + f[k][j]) f[i][j] = f[j][i] = f[i][k] + f[k][j]; } } } for(int i = 1; i <= n; i++){ for(int j = 0; j <= m; j++){ dp[i][j][0] = dp[i][j][1] = 1e9; } } dp[1][0][0] = dp[1][1][1] = 0; for(int i = 2; i <= n; i++){ for(int j = 0; j <= min(i, m); j++){ dp[i][j][0] = min(dp[i - 1][j][0] + f[c[i - 1]][c[i]], (dp[i - 1][j][1] + f[d[i - 1]][c[i]] * p[i - 1] + f[c[i - 1]][c[i]] * (1 - p[i - 1]))); if(j != 0) dp[i][j][1] = min(dp[i - 1][j - 1][0] + f[c[i - 1]][d[i]] * p[i] + f[c[i - 1]][c[i]] * (1 - p[i]), dp[i - 1][j - 1][1] + f[c[i - 1]][c[i]] * (1 - p[i]) * (1 - p[i - 1]) + f[c[i - 1]][d[i]] * (1 - p[i - 1]) * p[i] + f[d[i - 1]][c[i]] * p[i - 1] * (1 - p[i]) + f[d[i - 1]][d[i]] * p[i - 1] * p[i]); } } for(int j = 0; j <= m; j++) s = min(s, min(dp[n][j][0], dp[n][j][1])); printf("%.2lf", s); return 0; }
HDU3853 LOOPS
这道题的意思是:有一个R * C的迷宫布局,有个人想从起点(1, 1)出发,走到终点(R, C),他要走的话只能向下或者向下走,但每个格子都有让人停留在原地,往右走一个,往下走一格的概率,已知每走一格消耗2点能量,求出最后所需要的能量期望。
输入的时候,首先输入的是R和C,然后依次给出如果经过每个格子的时候,停在原地、向右走、向下走的概率,我们可以用一个三维数组a[i][j][0/1/2]把概率存起来,第三维012分别表示停在原地、向右走、向下走。这道题是期望dp,用逆推的思想求的期望,用dp[i][j]表示当人走到第i行第j列个格子的时候,要到终点(r, c)所需的期望能量,所以dp[r][c] = 0,我们目标是求dp[1][1]。状态转移:dp[i][j] = dp[i][j] * a[i][j][0] +dp[i][j + 1] *a[i][j][1] + dp[i + 1][j] * a[i][j][2] + 2。化简后可得:dp[i][j] = (dp[i][j + 1] * a[i][j][1] + dp[i + 1][j] * a[i][j][2] + 2) / (1 - a[i][j][0]);最后得到的dp[1][1]即为(1, 1)到终点(r, c)的能量期望。具体的代码实现如下:
#include <bits/stdc++.h> using namespace std; typedef long long LL; void debug_out(){ cerr << endl; } template<typename Head, typename... Tail> void debug_out(Head H, Tail... T){ cerr << " " << to_string(H); debug_out(T...); } #ifdef local #define debug(...) cerr<<"["<<#__VA_ARGS__<<"]:",debug_out(__VA_ARGS__) #else #define debug(...) 55 #endif double dp[1005][1005], a[1005][1005][3]; int main(){ ios::sync_with_stdio(false); cin.tie(0), cout.tie(0); int r, c; while(~scanf("%d%d", &r, &c)){ memset(dp, 0, sizeof dp); for(int i = 1; i <= r; i++){ for(int j = 1; j <= c; j++){ for(int k = 0; k <= 2; k++){ scanf("%lf", &a[i][j][k]); } } } for(int i = r; i >= 1; i--){ for(int j = c; j >= 1; j--){ if(i == r && j == c) continue; //终点初始化为0,不用转移 if(fabs(1 - a[i][j][0]) < 1e-9) continue; //a[i][j][0] == 1说明停在了这个格子了 dp[i][j] = (dp[i][j + 1] * a[i][j][1] + dp[i + 1][j] * a[i][j][2] + 2) / (1 - a[i][j][0]); debug(dp[i][j]); } } printf("%.3lf\n", dp[1][1]); } return 0; }
总结:
DP求期望的题目在对具体是求一个值或是最优化问题上会对方程得到转移方式有一些影响,但无论是DP求概率还是DP求期望,总是离不开概率知识和列出、化简计算公式的步骤,在写状态转移方程时需要思考的细节也类似。
-
插头dp
2020-09-14 20:58:17之前在讲状压dp时还没有了解过插头dp,但状压的最后一道例题已经和插头dp很像了,这节就来解决一个插头dp的入门问题。 插头dp学习之前需要掌握或了解的东西:状压dp,哈希表,状压用来压缩一些局面,但可能出现的...插头dp
之前在讲状压dp时还没有了解过插头dp,但状压的最后一道例题已经和插头dp很像了,这节就来解决一个插头dp的入门问题。
插头dp学习之前需要掌握或了解的东西:状压dp,哈希表,状压用来压缩一些局面,但可能出现的情况很多导致状压后的数很大,这时候就可以使用哈希表来仅存放已出现的局面,避免开辟太大的数组。
插头dp有几个关键词,当关键词出现时可以向这方面考虑:超小数据范围,网格图,连通性。
还需要理解一些抽象的定义:
插头
一个格子以某种方式向另一个格子相连,相连的位置叫插头,具体的类似拼图的凹槽与凸出这就是一种插头。
轮廓线
我们选取一个格子(i,j)作为决策点时,图中黄线就是轮廓线
轮廓线可以记录影响当前决策格或以后决策格做决策的要素(插头状态)。例题:URAL1519
题目大意:一个网格图中有若干障碍格子,求其他格子的哈密尔顿回路总数
题解
这道题的数据范围很小可以使用状态压缩,又要求连通性那就使用插头dp。
首先定义轮廓线设轮廓线的单位部分从左到右有a,b,c,d四个插头,我们发现如果a,c连通,那么b,d就不可能连通,这其实是一个括号匹配问题,于是我们可以进一步定义,如果a,b连通左边的a记为1,右边的b记为2。
这样每个轮廓线的单位部分就有了三种情况,三进制数不好运算我们可以使用四进制数记录。
16位的四进制数太大了我们需要一个方法减少一些空间使用,这就用到了哈希表通过哈希表我们可以只记录出现了的状态,其中大量的无意义的状态就不用储存了。
综上我们确定了我们的用于状态转移的状态 f ( i , j , S ) f(i,j,S) f(i,j,S)其中S为轮廓线状态。状态转移方程
mp数组是网格的状态,0为有障碍,1为无障碍。
每次转移我们需要将决策格的上,左边转移为下,右边。其中决策格的上,左边会影响到我们当前决策格的决策,为了方便我们将其记为b1,b2,设轮廓线为a0a1a2a3a4
1.当前决策格有障碍
那么只有这个格子没有连通的时候才是合法情况,转移后轮廓线状态不变。if(mp[i][j]){if(!b1&&!b2) ins(zt,num);}
其中ins()函数是向轮廓线状态zt的方案加上num(就是简化的 d p [ n o w ] [ z t ] + = d p [ l a s ] [ z t ‘ ] dp[now][zt]+=dp[las][zt`] dp[now][zt]+=dp[las][zt‘])。
2.当前决策无障碍:
(1)b1,b2都为0
那么只有决策格只有一种情况如图
转移后ai-1=1,ai=2。else if (!b1 && !b2) {if (mp[i + 1][j] && mp[i][j + 1]) ins(zt + bin[j - 1] + 2 * bin[j], num);}
这里即使不判断要连通的格子是不是有障碍,也可以正确给出答案,但是会额外在哈希表中创立许多无效方案,加大了时间复杂度与空间复杂度,所以这里选择在转移前多判断一下。
(2)b1与b2其中一个为0
b2=0时有两张情况,第一种交换ai-1与ai
第二种轮廓线不变
if(b1&&!b2){ if(mp[i][j+1]){ins(zt-bit[j-1]*b1+bit[j]*b1,num);} if(mp[i+1][j]){ins(zt,num);} }
b1=0时同理。
if(!b1&&b2){ if(mp[i][j+1]){ins(zt-bit[j]*b2+bit[j-1]*b2,num);} if(mp[i+1][j]){ins(zt,num);} }
(3)b1=b2
当b1=b2=1时,当b1与b2是不同的连线可以连线,但是b1与b2可能已经连上了,所以我们需要沿着轮廓线去寻找这条线是否已经连上了。(不是单纯沿轮廓线寻找一个为2的插头,因为中间可能还有更多没连上的线)
转移后ai-1,ai=0,要注意的是连线后要把左边的一个2插头改为1插头。if(b1==1&&b2==1){ int k=1; for(int t=j+1;t<=m;t++){ if((zt>>(2*t)%4)==1)k++; if((zt>>(2*t)%4)==2)k--; if(!k){ins(zt-bit[j]-bit[j-1]-bit[t],num);break;} } }
b1=b2=2时,同理。
if(b1==2&&b2==2){ int k=1; for(int t=j-2;t>=0;t--){ if((zt>>(2*t)%4==2)k++; if((zt>>(2*t)%4==1)k--; if(!k){ins(zt+bit[t]-bit[j]*2-bit[j-1]*2,num);break;} } }
(4)b1=2,b2=1
这个转移比较容易if(b1==2&&b2==1) ins(zt-bit[j]-bit[j-1]*2,num);
(5)b1=1,b2=2
这种情况一定要注意如果连线就提前形成一个回路,只有最后一个非障碍的格子才可以连起来,形成回路。完整代码
#include<iostream> using namespace std; const int MAX = 3e5 + 5, Has = 3e5 - 11; int n, m, e1, e2, las, now = 0; long long ans; int mp[15][15], bin[15], tot[2]; int h[MAX]; struct Hashtable//哈希表,a用来存轮廓线状态,js用来存方案数,next存放哈希冲突时下一个格子的坐标 { long long js[2]; int a[2], next; }has[MAX]; void ins(int zt, int num) { int tmp = zt % Has + 1; for (int i = h[tmp]; i; i = has[i].next) if (has[i].a[now] = zt) { has[i].js[now] += num; return; } has[++tot[now]].next = h[tmp]; h[tmp] = tot[now]; has[tot[now]].js[now] = num; has[tot[now]].a[now] = zt; } void work() { tot[now] = 1; has[1].a[now] = 0; has[1].js[now] = 1; for (int i = 1; i <= n; i++) { for (int j = 1; j <= tot[now]; j++)has[j].a[now] <<= 2;//换行转移 for (int j = 1; j <= m; j++) { las = now; now ^= 1; memset(h, 0, sizeof(h)); tot[now] = 0; for (int k = 1; k <= tot[las]; k++) { int zt = has[k].a[las]; long long num = has[k].js[las]; int b1 = (zt >> (2 * (j - 1))) % 4, b2 = (zt >> (2 * j)) % 4;//提取决策格上的轮廓线 if (!mp[i][j]) { if (!b1 && !b2)ins(zt, num); } else if (!b1 && !b2) { if (mp[i + 1][j] && mp[i][j + 1]) ins(zt + bin[j - 1] + 2 * bin[j], num); } else if (!b1&&b2) { if (mp[i][j + 1]) ins(zt, num); if (mp[i + 1][j]) ins(zt - bin[j] * b2 + bin[j - 1] * b2, num); } else if (b1 && !b2) { if (mp[i][j + 1]) ins(zt - bin[j - 1] * b1 + bin[j] * b1, num); if (mp[i + 1][j]) ins(zt, num); } else if (b1 == 1 && b2 == 1) { int kl = 1; for (int t = j + 1; t <= m; ++t) { if ((zt >> (t * 2)) % 4 == 1) ++kl; if ((zt >> (t * 2)) % 4 == 2) --kl; if (!kl) { ins(zt - bin[j] - bin[j - 1] - bin[t], num); break; } } } else if (b1 == 2 && b2 == 2) { int kl = 1; for (int t = j - 2; t >= 0; --t) { if ((zt >> (t * 2)) % 4 == 1) --kl; if ((zt >> (t * 2)) % 4 == 2) ++kl; if (!kl) { ins(zt + bin[t] - 2 * bin[j] - 2 * bin[j - 1], num); break; } } } else if (b1 == 2 && b2 == 1) ins(zt - 2 * bin[j - 1] - bin[j], num); else if (i == e1 && j == e2) ans += num; } } } } int main() { cin >> n >> m; for (int i = 1; i <= n; i++) { for (int j = 1; j <= m; j++) { char ch; ch = getchar(); while (ch != '*'&&ch != '.')ch = getchar(); if (ch == '.') { mp[i][j] = 1; e1 = i; e2 = j; } } } bin[0] = 1; for (int i = 1; i <= 12; i++)bin[i] = bin[i - 1] << 2; work(); cout << ans << endl; system("pause"); return 0; }
本题除了转移方程的策略选择,还有哈希表的构造,本题哈希需要存储轮廓线状态,方案数两种数据各两次,这里使用了一个结构体包装,如果拆成单个数组也可以通过相同的索引调用数据。
本题的哈希表处理哈希冲突的方式是链表法,将冲突的元素通过next连接到了链表头。
这里的代码我发现与储存图的链式向前星相似(都是用数组写链表)可以结合理解。
还有本题用到了滚动数组减少空间,之前状压dp也讲到了。 -
【学习笔记】简单的连通性状压DP——插头DP(不学以为是天书)
2022-01-02 22:08:16文章目录 哈希链表 插头DP 概念 括号表示法 / 最小表示法 例题 洛谷插头dp板题 CITY ParkII Tony's Tour Efficient Tree [CQOI2015]标识设计 哈希链表 众所周知,哈希是有冲突的可能性的,而且在状态数越多,冲突的...哈希链表
众所周知,哈希是有冲突的可能性的,而且在状态数越多,冲突的概率就越高。目前掌握的处理方案有多哈希,但仍有冲突的可能; STL \text{STL} STL 直接整个记录下来,自带大常数和 log \text{log} log。
插头 DP 都不用,而是采取了哈希链表的方法。具体而言就是将轮廓线上插头状态按一定的规则哈希成一个整数后,甩到其对应的链上。
形象地说,就是开了一定的哈希桶,然后哈希后的整数取模桶数,得到一个桶的编号,接着把这个轮廓线相应信息装成结构体,放到这个桶里。显然这个桶里很有可能有其余的轮廓线状态,那么就直接接在最后一个的后面。用前向星,数组来做。
应该不会有人要刚vector吧桶数随意,但肯定是越大且是个质数更好,因为后面定位轮廓线哈希位置的时候,是要从其所在桶里面开始一个一个遍历比较的,如果一个桶内太多轮廓线状态,遍历时间复杂度就有点要命了。
#define mod 299989 struct HashTable { int sta[2], dp[2], nxt; }Hash[300000]; void insert( int sta, int val ) { int key = sta % mod; for( int i = head[key];i;i = Hash[i].nxt ) if( sta == Hash[i].sta[now] ) { Hash[i].dp[now] += val; return; } ++ cnt[now]; Hash[cnt[now]].sta[now] = sta; Hash[cnt[now]].dp[now] = val; Hash[cnt[now]].nxt = head[key]; head[key] = cnt[now]; };
插头DP
概念
插头DP
,是一类基于连通性的状态压缩动态规划,用状压DP来处理联通问题。本质就是状压。常见的联通问题:多回路问题、路径问题、简单回路问题、广义路径问题、生成树问题。
插头DP 一般是 逐格转移 的,少有逐行转移。
而逐格转移就是将格子划分成已转移的格子和未转移的格子,我们将起到这样分类作用的工具叫做 轮廓线。
如图,红色线就是此时的轮廓线,当前在处理的格子是黄色格子,也就是说当前处理的格子也被划分到未转移的格子集合中。
不难发现, m m m 列却有 m + 1 m+1 m+1 个插头 / 轮廓线。
既然叫做 插头DP,那么什么又是插头呢?插头就是一个格子上下左右四个方向的插头,如图。
前面提到了主要是用来解决连通性问题的,一个格子与其余格子联通,怎么联通的
这个插头可以帮助我们知道两个相邻格子是怎样连接的,比如这个格子是和上面格子联通的,那么就是一条上下边,是通过这个格子的上插头完成的。还有如果这个格子恰好是联通的拐点,就是通过相邻插头,比如从左插头联通这个格子又从下插头连出去。
一个格子有四个插头,一个存在的插头表示 在它代表的方向上 能与相邻的格子连接(联通)。不存在就不能。
要求一个回路,也就意味着最后所有的非障碍格子通过插头连接成了一个连通块,那么久需要转移时记录格子的连通情况。
我们递推的时候就是依据轮廓线上插头的存在性,求出所有能转移到的合法状态。
形象地理解,每个格子可以看作一块块拼图,插头就是两块拼图之间的衔接。
在逐格转移中一般只记录轮廓线上的插头存在性,因为这些才与后面的格子是有可能直接相连的。
转移到新格子后,轮廓线也会相应的移动。如图。不难发现,同行内的移动只跟当前处理格子的左插头和上插头有关,并且是转移到自己的右插头和下插头。如果换行,发现唯一一个竖着的特殊插头是不会有的。
但不影响,后面会提到。
所以当前格子合法状态至于上一次处理的格子有关,这里就可以采用滚动数组优化了,减少空间花费。一般是设 d p [ i ] [ j ] [ s t a ] : ( i , j ) dp[i][j][sta]:(i,j) dp[i][j][sta]:(i,j) 位置时状态是 s t a sta sta 的方案数 / 代价和 等等。状压的就是轮廓线状态。
括号表示法 / 最小表示法
记录当前的联通状态 / 轮廓线上的插头状态,准确地讲是记录轮廓线上的状态,一般有两种方法。
括号表示法
当前已经联通的轮廓线上的插头,靠左边的是左括号,靠右边的是右括号。没有插头就另设字符。
轮廓线上从左到右 a , b , c , d a,b,c,d a,b,c,d 插头,如果 a , c a,c a,c 连通,并且与 b b b 不连通,那么 b , d b,d b,d 一定不连通。这个性质对所有的棋盘模型的问题都适用。
感性理解这很显然。
从左到右的排序是从左边的第一条轮廓线走到右边第一条轮廓线依次经历轮廓线的顺序。
最小表示法
同样地,从左到右的顺序,找到第一个不是障碍的轮廓线插头,然后找到跟这个插头联通的其余轮廓线插头,标记为第一个连通块,然后找第二个不是障碍且没有标记的插头,以此类推。
最小表示法比较好写,但括号表示法似乎时间更优秀。括号表示法是要每种情况分类讨论的,回路到还好只有三种状态,只用讨论九种,要是简单路径就会涉及到单独插头的问题,就是讨论十六种了。写挂的概率直线飙升。
最小表示法是有些情况可以合并成一个写。
且括号表示法的状态修改较为麻烦,都不一样,所以无法合并情况,而最小表示法比较暴力直接解码重编。
竖着的那条轮廓线比较特殊,所以我一般把它放到第 0 0 0 位。
例题
由于涉及到哈希压缩,一般都是用位运算,所以有些题目虽然是列的上限是 5 5 5 这种,我们也习惯开成 8 8 8 位的,这在最小表示法中很常见。
当你题目做多了过后,就会发现基本上都是一样的框架的感觉。
洛谷插头dp板题
此题就用括号表示法来做吧。
-
新建一个连通块
这个新建是就当前已操作过的格子而言的,但本题肯定是最后会联通成一个的,否则就不合法了。
能新建联通块当且仅当这个格子的上边轮廓线和左边轮廓线都没有插头。如图。
-
合并两个联通块
那么肯定是两个轮廓线都指了插头,这里必须做合并操作,不然就无法形成回路。
- 合并的是两个不同连通块的右括号,那么就要找两个右括号相对应的左括号更靠右的一个,变成右括号。
- 合并的是两个不同连通块的左括号,那么就要找两个左括号相对应的右括号更靠左的一个,变成左括号。
-
合并的是两个联通块的左右括号,直接擦去即可。
最后一个格子肯定是也是合并的这个类型,形成了完整的一条回路,这个时候还需要判断是否轮廓上一个插头都不存在,是否合法,然后统计答案。
-
延续之前的联通情况。
-
不拐弯。
不拐弯最简单,不用改轮廓线情况,直接插入就行。
注意虽然下面这张图的括号表示法看似发生了改变,但是前面我提过,我喜欢把竖着个特殊轮廓线放在第 0 0 0 位,所以是没有改变的。
具体可见代码。
有的人就喜欢在 ( i , j ) (i,j) (i,j) 时, j j j 代表格子横着的轮廓线, j − 1 j-1 j−1 代表特殊的竖轮廓线。那可能就需要修改??
-
拐弯的。
拐弯的其实也简单,就是直接延续。虽然括号表示法看起来没有变化,但实际上是有轮廓线改变的。
具体可见代码。
-
#include <bits/stdc++.h> using namespace std; #define mod 298999 #define int long long int n, m; int lst, now;//滚动 int head[300000], cnt[2]; //滚动的总合法方案数 bool mp[15][15]; //0 1 2 没有插头 左括号 右括号 struct HashTable { int sta[2], dp[2], nxt; }Hash[300000]; void insert( int sta, int val ) { int key = sta % mod; for( int i = head[key];i;i = Hash[i].nxt ) if( sta == Hash[i].sta[now] ) { Hash[i].dp[now] += val; return; } ++ cnt[now]; Hash[cnt[now]].sta[now] = sta; Hash[cnt[now]].dp[now] = val; Hash[cnt[now]].nxt = head[key]; head[key] = cnt[now]; }; struct node { int s[15]; }; node unZip( int sta ) { //解压 node code; code.s[0] = sta & 3; //单独的竖直轮廓线 for( int i = 1;i <= m;i ++ ) code.s[i] = ( sta >> ( i << 1 ) ) & 3; return code; } int Zip( node code ) { //压缩 int sta = 0; for( int i = 1;i <= m;i ++ ) sta |= ( code.s[i] << ( i << 1 ) ); sta |= code.s[0]; return sta; } signed main() { int ans = 0, Endx, Endy; scanf( "%lld %lld", &n, &m ); char ch[20]; for( int i = 1;i <= n;i ++ ) { scanf( "%s", ch + 1 ); for( int j = 1;j <= m;j ++ ) if( ch[j] == '.' ) mp[i][j] = 1, Endx = i, Endy = j; } insert( 0, 1 ); for( int i = 1;i <= n;i ++ ) { for( int j = 1;j <= m;j ++ ) { lst = now, now ^= 1, cnt[now] = 0; memset( head, 0, sizeof( head ) ); for( int k = 1;k <= cnt[lst];k ++ ) { node code = unZip( Hash[k].sta[lst] ); int Left = code.s[0], Up = code.s[j]; //左插头 上插头 int dp = Hash[k].dp[lst]; if( ! mp[i][j] ) { if( ! Left and ! Up ) insert( Zip( code ), dp ); } else if( ! Left and ! Up ) { if( mp[i + 1][j] and mp[i][j + 1] ) { code.s[0] = 2, code.s[j] = 1; insert( Zip( code ), dp ); } } else if( ! Left and Up ) { if( mp[i + 1][j] ) insert( Zip( code ), dp ); if( mp[i][j + 1] ) { code.s[0] = Up, code.s[j] = 0; insert( Zip( code ), dp ); } } else if( Left and ! Up ) { if( mp[i][j + 1] ) insert( Zip( code ), dp ); if( mp[i + 1][j] ) { code.s[0] = 0, code.s[j] = Left; insert( Zip( code ), dp ); } } else if( Left == 1 and Up == 1 ) { //不属于同一个连通块 都是左括号 //得连起来 然后与这两个左括号匹配的右括号中较近的一个改成左括号 方法使用括号匹配 //显然肯定是左插头的匹配括号在右 呈包含关系 int p, tot = 1; for( p = j + 1;p <= m;p ++ ) { if( code.s[p] == 1 ) tot ++; if( code.s[p] == 2 ) tot --; if( ! tot ) break; } code.s[0] = code.s[j] = 0, code.s[p] = 1; insert( Zip( code ), dp ); } else if( Left == 2 and Up == 2 ) { //显然肯定是上插头的匹配括号在左 呈包含关系 int p, tot = -1; for( p = j - 1;p;p -- ) { if( code.s[p] == 1 ) tot ++; if( code.s[p] == 2 ) tot --; if( ! tot ) break; } code.s[0] = code.s[j] = 0, code.s[p] = 2; insert( Zip( code ), dp ); } else if( Left == 2 and Up == 1 ) { code.s[0] = code.s[j] = 0; insert( Zip( code ), dp ); } else if( Left == 1 and Up == 2 ) { //回路形成 code.s[0] = code.s[j] = 0; bool flag = 0;//判断是否合法 for( int p = 0;p <= m;p ++ ) if( code.s[i] ) { flag = 1; break; } if( ! flag and i == Endx and j == Endy ) ans += dp; } } } } printf( "%lld\n", ans ); return 0; }
CITY
如果板题看懂了,就会发现这道题只是有些限制需要判定而已。直接改改就能过。
#include <bits/stdc++.h> using namespace std; #define mod 298999 #define int long long int n, m; int lst, now;//滚动 int head[300000], cnt[2]; //滚动的总合法方案数 int mp[15][15]; //0 1 2 没有插头 左括号 右括号 struct HashTable { int sta[2], dp[2], nxt; }Hash[300000]; void insert( int sta, int val ) { int key = sta % mod; for( int i = head[key];i;i = Hash[i].nxt ) if( sta == Hash[i].sta[now] ) { Hash[i].dp[now] += val; return; } ++ cnt[now]; Hash[cnt[now]].sta[now] = sta; Hash[cnt[now]].dp[now] = val; Hash[cnt[now]].nxt = head[key]; head[key] = cnt[now]; }; struct node { int s[15]; }; node unZip( int sta ) { //解压 node code; code.s[0] = sta & 3; //单独的竖直轮廓线 for( int i = 1;i <= m;i ++ ) code.s[i] = ( sta >> ( i << 1 ) ) & 3; return code; } int Zip( node code ) { //压缩 int sta = 0; for( int i = 1;i <= m;i ++ ) sta |= ( code.s[i] << ( i << 1 ) ); sta |= code.s[0]; return sta; } signed main() { int ans = 0, Endx, Endy; scanf( "%lld %lld", &n, &m ); char ch[20]; for( int i = 1;i <= n;i ++ ) { scanf( "%s", ch + 1 ); for( int j = 1;j <= m;j ++ ) { if( ch[j] == '#' ) continue; if( ch[j] == '.' ) mp[i][j] = 1; if( ch[j] == '-' ) mp[i][j] = 2; if( ch[j] == '|' ) mp[i][j] = 3; Endx = i, Endy = j; } } insert( 0, 1 ); for( int i = 1;i <= n;i ++ ) { for( int j = 1;j <= m;j ++ ) { lst = now, now ^= 1, cnt[now] = 0; memset( head, 0, sizeof( head ) ); for( int k = 1;k <= cnt[lst];k ++ ) { node code = unZip( Hash[k].sta[lst] ); int Left = code.s[0], Up = code.s[j]; //左插头 上插头 int dp = Hash[k].dp[lst]; if( ! mp[i][j] ) { if( ! Left and ! Up ) insert( Zip( code ), dp ); } else if( ! Left and ! Up ) { if( mp[i][j] == 1 and mp[i + 1][j] and mp[i][j + 1] ) { code.s[0] = 2, code.s[j] = 1; insert( Zip( code ), dp ); } } else if( ! Left and Up ) { if( ( mp[i][j] == 3 or mp[i][j] == 1 ) and mp[i + 1][j] ) insert( Zip( code ), dp ); if( mp[i][j] == 1 and mp[i][j + 1] ) { code.s[0] = Up, code.s[j] = 0; insert( Zip( code ), dp ); } } else if( Left and ! Up ) { if( ( mp[i][j] == 1 or mp[i][j] == 2 ) and mp[i][j + 1] ) insert( Zip( code ), dp ); if( mp[i][j] == 1 and mp[i + 1][j] ) { code.s[0] = 0, code.s[j] = Left; insert( Zip( code ), dp ); } } else if( Left == 1 and Up == 1 and mp[i][j] == 1 ) { //不属于同一个连通块 都是左括号 //得连起来 然后与这两个左括号匹配的右括号中较近的一个改成左括号 方法使用括号匹配 //显然肯定是左插头的匹配括号在右 呈包含关系 int p, tot = 1; for( p = j + 1;p <= m;p ++ ) { if( code.s[p] == 1 ) tot ++; if( code.s[p] == 2 ) tot --; if( ! tot ) break; } code.s[0] = code.s[j] = 0, code.s[p] = 1; insert( Zip( code ), dp ); } else if( Left == 2 and Up == 2 and mp[i][j] == 1 ) { //显然肯定是上插头的匹配括号在左 呈包含关系 int p, tot = -1; for( p = j - 1;p;p -- ) { if( code.s[p] == 1 ) tot ++; if( code.s[p] == 2 ) tot --; if( ! tot ) break; } code.s[0] = code.s[j] = 0, code.s[p] = 2; insert( Zip( code ), dp ); } else if( Left == 2 and Up == 1 and mp[i][j] == 1 ) { code.s[0] = code.s[j] = 0; insert( Zip( code ), dp ); } else if( Left == 1 and Up == 2 and mp[i][j] == 1 ) { //回路形成 code.s[0] = code.s[j] = 0; bool flag = 0;//判断是否合法 for( int p = 0;p <= m;p ++ ) if( code.s[i] ) { flag = 1; break; } if( ! flag and i == Endx and j == Endy ) ans += dp; } } } } printf( "%lld\n", ans ); return 0; }
ParkII
这道题就是求一条简单路径,那么就不要求一定是个回路,这个时候如果采取括号表示法讨论就有点多了。
最小表示法就较好写一点,多压一个路径的端点数量即可,最后的合法结果一定有且只有两个端点。也就是单独插头。
#include <bits/stdc++.h> using namespace std; #define mod 298999 #define ll long long int n, m, num, lst, now; //num:单独插头的个数 int cnt[2], head[300000]; int v[105][10]; struct HashTable { int sta[2], nxt;ll dp[2]; }Hash[300000]; void insert( int sta, ll val ) { int key = sta % mod; for( int i = head[key];i;i = Hash[i].nxt ) if( Hash[i].sta[now] == sta ) { Hash[i].dp[now] = max( val, Hash[i].dp[now] ); return; } ++ cnt[now]; Hash[cnt[now]].sta[now] = sta; Hash[cnt[now]].dp[now] = val; Hash[cnt[now]].nxt = head[key]; head[key] = cnt[now]; } struct node { int s[15]; }; int vis[10]; int Zip( node code ) { int sta = 0, tot = 0; for( int i = 1;i <= 6;i ++ ) vis[i] = 0; for( int i = 0;i <= m;i ++, sta <<= 3 ) { if( ! code.s[i] ) continue; if( ! vis[code.s[i]] ) vis[code.s[i]] = ++ tot; //找最小表示 sta |= vis[code.s[i]]; } sta |= num; return sta; } node unZip( int sta ) { node code; num = sta & 7; for( int i = m;~ i;i -- ) sta >>= 3, code.s[i] = sta & 7; return code; } int main() { scanf( "%d %d", &n, &m ); for( int i = 1;i <= n;i ++ ) for( int j = 1;j <= m;j ++ ) scanf( "%d", &v[i][j] ); insert( 0, 0 ); for( int i = 1;i <= n;i ++ ) for( int j = 1;j <= m;j ++ ) { lst = now, now ^= 1, cnt[now] = 0; memset( head, 0, sizeof( head ) ); for( int k = 1;k <= cnt[lst];k ++ ) { node code = unZip( Hash[k].sta[lst] ); ll dp = Hash[k].dp[lst] + v[i][j]; int left = code.s[0], up = code.s[j]; if( left and up ) { if( left ^ up ) { //两个插头不是同一个连通块 在(i,j)位置合并两个连通块 code.s[0] = code.s[j] = 0;//横着和竖着的轮廓线都要被擦掉 for( int p = 0;p <= m;p ++ ) if( code.s[p] == up ) code.s[p] = left; insert( Zip( code ), dp ); } } else if( left or up ) { //合并两种情况 int id = left + up; if( i < n ) { code.s[j] = id, code.s[0] = 0; insert( Zip( code ), dp ); } if( j < m ) { code.s[0] = id, code.s[j] = 0; insert( Zip( code ), dp ); } if( num < 2 ) { code.s[j] = code.s[0] = 0, num ++; insert( Zip( code ), dp ); } } else { insert( Zip( code ), Hash[k].dp[lst] );//两边都没有插头 可以选择不选这个格子 if( i < n and j < m ) {//一个新连通块的中转点 code.s[j] = code.s[0] = 6;//用最大的填 保证编号不与已存在的连通块冲突 insert( Zip( code ), dp ); } if( num < 2 ) { //直接做一个单独插头 不是路径的起点就是终点 num ++; if( i < n ) { code.s[j] = 6, code.s[0] = 0; insert( Zip( code ), dp ); } if( j < m ) { code.s[j] = 0, code.s[0] = 6; insert( Zip( code ), dp ); } } } } } ll ans = -1e18; for( int i = 1;i <= cnt[now];i ++ ) if( ( Hash[i].sta[now] & 7 ) == 2 ) ans = max( ans, Hash[i].dp[now] ); printf( "%lld\n", ans ); return 0; }
Tony’s Tour
还要简单一点,稍微转化一下,在棋盘最后加入两行。
.####.
. . . . . .
就让起点和终点联通形成回路了,且这两行的走法之有一种。
#include <bits/stdc++.h> using namespace std; #define mod 298999 bool mp[15][15]; int head[300000], cnt[2]; int lst, now, n, m; struct HashTable { int sta[2], dp[2], nxt; }Hash[300000]; void insert( int sta, int val ) { int key = sta % mod; for( int i = head[key];i;i = Hash[i].nxt ) if( Hash[i].sta[now] == sta ) { Hash[i].dp[now] += val; return; } ++ cnt[now]; Hash[cnt[now]].sta[now] = sta; Hash[cnt[now]].dp[now] = val; Hash[cnt[now]].nxt = head[key]; head[key] = cnt[now]; } struct node { int s[15]; }; int Zip( node code ) { int sta = 0; for( int i = 1;i <= m;i ++ ) sta |= ( code.s[i] << ( i << 1 ) ); sta |= code.s[0]; return sta; } node unZip( int sta ) { node code; code.s[0] = sta & 3; for( int i = 1;i <= m;i ++ ) code.s[i] = ( sta >> ( i << 1 ) ) & 3; return code; } int main() { char ch[15]; while( scanf( "%d %d", &n, &m ) and n and m ) { memset( mp, 0, sizeof( mp ) ); //因为多组数据且后面没有判断是否(i+1,j)(i,j+1)在棋盘内 所以要全都清空 避免上一轮的mp有的地方为1 for( int i = 1;i <= n;i ++ ) { scanf( "%s", ch + 1 ); for( int j = 1;j <= m;j ++ ) if( ch[j] == '.' ) mp[i][j] = 1; else mp[i][j] = 0; } mp[n + 1][1] = mp[n + 1][m] = 1; for( int i = 2;i < m;i ++ ) mp[n + 1][i] = 0; for( int i = 1;i <= m;i ++ ) mp[n + 2][i] = 1; n += 2; now = 0, cnt[now] = 0; memset( head, 0, sizeof( head ) ); insert( 0, 1 ); int ans = 0; for( int i = 1;i <= n;i ++ ) for( int j = 1;j <= m;j ++ ) { lst = now, now ^= 1, cnt[now] = 0; memset( head, 0, sizeof( head ) ); for( int k = 1;k <= cnt[lst];k ++ ) { node code = unZip( Hash[k].sta[lst] ); int left = code.s[0], up = code.s[j]; int dp = Hash[k].dp[lst]; if( ! mp[i][j] ) { if( ! left and ! up ) insert( Zip( code ), dp ); } else if( ! left and ! up ) { if( mp[i + 1][j] and mp[i][j + 1] ) { code.s[0] = 2, code.s[j] = 1; insert( Zip( code ), dp ); } } else if( ! left and up ) { if( mp[i + 1][j] ) insert( Zip( code ), dp ); if( mp[i][j + 1] ) { code.s[0] = up, code.s[j] = 0; insert( Zip( code ), dp ); } } else if( left and ! up ) { if( mp[i][j + 1] ) insert( Zip( code ), dp ); if( mp[i + 1][j] ) { code.s[j] = left, code.s[0] = 0; insert( Zip( code ), dp ); } } else if( left == 2 and up == 1 ) { code.s[0] = code.s[j] = 0; insert( Zip( code ), dp ); } else if( left == 1 and up == 1 ) { int p, tot = 1; for( p = j + 1;p <= m;p ++ ) { if( code.s[p] == 1 ) tot ++; if( code.s[p] == 2 ) tot --; if( ! tot ) break; } code.s[0] = code.s[j] = 0, code.s[p] = 1; insert( Zip( code ), dp ); } else if( left == 2 and up == 2 ) { int p, tot = -1; for( p = j - 1;p;p -- ) { if( code.s[p] == 1 ) tot ++; if( code.s[p] == 2 ) tot --; if( ! tot ) break; } code.s[0] = code.s[j] = 0, code.s[p] = 2; insert( Zip( code ), dp ); } else if( left == 1 and up == 2 ) { code.s[0] = code.s[j] = 0; bool flag = 1; for( int p = 0;p <= m;p ++ ) if( code.s[p] ) { flag = 0; break; } if( flag and i == n and j == m ) ans += dp; } } } printf( "%d\n", ans ); } return 0; }
Efficient Tree
也是轮廓线 D P DP DP 的题目,直接分类讨论就行。
#include <bits/stdc++.h> using namespace std; #define int long long #define mod 1000000007 struct node { int ans, cnt; node operator + ( node &now ) const { if( ans < now.ans ) return *this; else if( ans > now.ans ) return now; else return { ans, ( cnt + now.cnt ) % mod }; } node operator + ( int x ) { return { ans + x, cnt }; } node operator * ( int x ) { return { ans, cnt * x % mod }; }; }; int L[1000][1000], U[1000][1000]; int lst, now, n, m; int cnt[2], head[2500]; struct HASH { node dp[2]; int sta[2], nxt; }Hash[3000000]; void insert( int sta, node cost ) { int key = sta % 2333; for( int i = head[key];i;i = Hash[i].nxt ) if( Hash[i].sta[now] == sta ) { Hash[i].dp[now] = Hash[i].dp[now] + cost; return; } ++ cnt[now]; Hash[cnt[now]].sta[now] = sta; Hash[cnt[now]].dp[now] = cost; Hash[cnt[now]].nxt = head[key]; head[key] = cnt[now]; } int vis[10]; struct zip { int s[15]; zip(){ memset( s, 0, sizeof( s ) ); } /* 注意清空 因为第i行最后1列跳转到第i+行第1列的时候会访问到第0列的状态 呼应flag单独联通块的判断 */ }; int encode( zip code ) { int sta = 0, tot = 0; memset( vis, -1, sizeof( vis ) ); vis[0] = 0; for( int i = 1;i <= m;i ++ ) { if( vis[code.s[i]] == -1 ) vis[code.s[i]] = ++ tot; sta = ( sta << 3 ) | vis[code.s[i]]; } return sta; } zip decode( int sta ) { zip code; for( int i = m;i;i --, sta >>= 3 ) code.s[i] = sta & 7; return code; } signed main() { int T; scanf( "%lld", &T ); for( int t = 1;t <= T; t++ ) { scanf( "%lld %lld", &n, &m ); for( int i = 1;i <= n;i ++ ) for( int j = 2;j <= m;j ++ ) scanf( "%lld", &L[i][j] ); for( int i = 2;i <= n;i ++ ) for( int j = 1;j <= m;j ++ ) scanf( "%lld", &U[i][j] ); now = 0, cnt[now] = 0; memset( head, 0, sizeof( head ) ); insert( 0, { 0, 1 } ); for( int i = 1;i <= n;i ++ ) for( int j = 1;j <= m;j ++ ) { lst = now, now ^= 1, cnt[now] = 0; memset( head, 0, sizeof( head ) ); for( int k = 1;k <= cnt[lst];k ++ ) { zip code = decode( Hash[k].sta[lst] ); int left = code.s[j - 1], up = code.s[j]; node dp = Hash[k].dp[lst]; bool flag = 1; for( int p = 0;p <= m;p ++ ) if( p ^ j and code.s[p] == up ) { flag = 0; break; } if( j > 1 and ! flag ) { code.s[j] = left; insert( encode( code ), { dp.ans + L[i][j], dp.cnt * 2 % mod } ); code.s[j] = up; } if( i > 1 ) insert( encode( code ), { dp.ans + U[i][j], dp.cnt * 2 % mod } ); if( ! flag ) { code.s[j] = 8; //赋值成不可能有的最小表示法到达的连通块编号数量 表示新开一个连通块 insert( encode( code ), dp ); code.s[j] = up; } if( i > 1 and j > 1 and left ^ up ) { for( int p = 0;p <= m;p ++ ) if( code.s[p] == left ) code.s[p] = up; insert( encode( code ), { dp.ans + U[i][j] + L[i][j], dp.cnt * 3 % mod } ); } } } node ans = { 0x7f7f7f7f, 0 }; for( int i = 1;i <= cnt[now];i ++ ) { bool flag = 1; zip code = decode( Hash[i].sta[now] ); for( int j = 1;j < m;j ++ ) flag &= ( code.s[j] == code.s[j + 1] ); if( flag ) ans = ans + Hash[i].dp[now]; } printf( "Case #%lld: %lld %lld\n", t, ans.ans, ans.cnt ); } return 0; }
[CQOI2015]标识设计
BZOJ3934
将 L L L 形状的表示拆分成 一个只有下插头,一段上下插头,一个有上插头和右插头,一段左右插头,一个只有左插头 五个部分。记录转折插头的个数和只有左插头的个数。
当转折插头个数有 3 3 3 个,只有左插头的个数已经有 2 2 2 个了。当现在这个格子成为左插头就形成了 3 3 3 个 L L L 标识。统计进入答案即可。
当然这一切都要在合法的情况下进行插头转移。
#include <bits/stdc++.h> using namespace std; #define int long long int lst, now, ans; int cnt[2], head[300000]; bool ch[50][50]; struct HashTable { int sta[2], dp[2], nxt; }Hash[700000]; void insert( int sta, int val ) { int key = sta % 299989; for( int i = head[key];i;i = Hash[i].nxt ) if( Hash[i].sta[now] == sta ) { Hash[i].dp[now] += val; return; } ++ cnt[now]; Hash[cnt[now]].sta[now] = sta; Hash[cnt[now]].dp[now] = val; Hash[cnt[now]].nxt = head[key]; head[key] = cnt[now]; } int zip( int x, int y, int z ) { return ( x << 4 ) | ( y << 2 ) | z; } signed main() { int n, m; char s[50]; scanf( "%lld %lld", &n, &m ); for( int i = 1;i <= n;i ++ ) { scanf( "%s", s + 1 ); for( int j = 1;j <= m;j ++ ) ch[i][j] = s[j] == '.'; } insert( 0, 1 ); for( int i = 1;i <= n;i ++ ) { for( int k = 1;k <= cnt[now];k ++ ) Hash[k].sta[now] = (Hash[k].sta[now] & 15) | (Hash[k].sta[now] >> 4 << 5); for( int j = 1;j <= m;j ++ ) { lst = now, now ^= 1, cnt[now] = 0; memset( head, 0, sizeof( head ) ); for( int k = 1;k <= cnt[lst];k ++ ) { int sta = Hash[k].sta[lst] >> 4, dp = Hash[k].dp[lst]; int left = sta >> j - 1 & 1, up = sta >> j & 1; int num = Hash[k].sta[lst] >> 2 & 3; int tot = Hash[k].sta[lst] & 3; if( up and left ) continue; //这个格子连出去两个格子 不合法 形成的是反L形 else if( ! ch[i][j] ) { if( ! left and ! up ) insert( zip(sta, num, tot), dp ); } else if( ! left and ! up ) { insert( zip(sta, num, tot), dp ); if( num < 3 and ch[i + 1][j] ) insert( zip((1 << j - 1) | sta, num + 1, tot), dp ); } else if( ! left and up ) { if( ch[i][j + 1] ) insert( zip(sta, num, tot), dp ); if( ch[i + 1][j] ) insert( zip(sta ^ (1 << j - 1) ^ (1 << j), num, tot), dp ); } else { if( ch[i][j + 1] ) insert( zip(sta ^ (1 << j - 1) ^ (1 << j), num, tot), dp ); if( num == 3 and tot == 2 ) ans += dp; else insert( zip(sta ^ (1 << j - 1), num, tot + 1), dp ); } } } } printf( "%lld\n", ans ); return 0; }
-
-
插头DP
2019-09-27 15:43:07插头DP主要用来处理一系列基于连通性状态压缩的动态规划问题,处理的具体问题有很多种,并且一般数据规模较小。 由于棋盘有很特殊的结构,使得它可以与“连通性”有很强的联系,因此插头DP最常见的应用要数在棋盘... -
插头DP论文
2013-05-27 13:53:18基于连通性状态压缩的动态规划问题 长沙市雅礼中学 陈丹琦 【摘要】 基于状态压缩的动态规划问题是一类以集合信息为状态且状态总数为指数级的特殊的动态规划问题.在状态压缩的基础上,有一类问题的状态中必须要... -
插头DP学习笔记
2018-09-18 10:06:26hhh还是滚去学了插头DP。。。 这玩意理解起来其实并不是听说的那么困难。(那是因为你只写了板子QAQ 我太菜了所以可能写了一堆锅,所以哪位爸爸发现了错误指出来就好。谢谢orz! 基本概念 Q:插头DP是啥? A:... -
插头DP模板待完成.md
2021-02-23 17:27:35未完成的DP -
插头dp ——从入门到跳楼
2018-02-25 15:33:32Q:什么题目使用插头dp? A:关键词:超小数据范围,网格图,连通性。 Q:什么是“插头”? A:一个格子通过某些方向与另一个格子相连,这些连接的位置叫做“插头”。形象地理解,网格图上每一个格子是一块拼图,那么... -
插头DP_最小表示法 模板详解
2018-04-30 13:05:44声明模板来自:https://www.cnblogs.com/kuangbin/archive/2012/09/29/2708989.html算法说明如果还不知道插头dp中插头以及轮廓线等概念是什么东西的话,请移步:插头与轮廓线与基于连通性状态压缩的动态规划然后对于... -
插头DP/轮廓线DP
2022-02-09 06:12:54题解 P5056 【【模板】插头dp】- GNAQ (\(\uparrow\) 学习资料,大部分贺的,有一些些的改动与自己的补充) 什么是插头 DP 插头 DP 是一类用状压 DP 来处理连通性问题的 DP 方法。 常见的类型:棋盘插头 DP、连通性... -
插头 dp 总结
2019-10-08 13:08:22插头 dp 主要用来处理一系列基于连通性状态压缩的动态规划问题,处理的具体问题有很多种,并且一般数据规模较小。由于棋盘有很特殊的结构,使得它可以与“连通性”有很强的联系,因此插头 dp 最常见的应用要数在... -
区间DP概率DP树形DP插头DP
2015-09-05 13:37:49区间DP概率DP树形DP插头DP,每种DP一道典型例题,有助于初学者 -
插头dp小结
2021-01-25 16:06:58都1202年了,怎么还有人不会轮廓线dp啊,明明8002年就有论文了… 参考资料: cdqcdqcdq, a_forever_kinga\_forever\_kinga_forever_king 轮廓线 dpdpdp本质上是一种基于连通性状态压缩的动态规划. 例题1 ... -
插头DP入门
2019-10-08 20:50:10终于来补插头DP的坑了,咕了好久,主要是因为博猪代码实现能力太弱,而网上的大神们都只讲分类讨论。。。 只放代码了: zzh学长: 1 #include<bits/stdc++.h> 2 using namespace std; 3 #... -
插头dp初探
2019-02-22 10:33:00插头dp用于解决一类可基于图连通性递推的问题。用插头来表示轮廓线上的连通性,然后根据连通性与下一位结合讨论进行转移。 表示连通性的方法 与字符串循环最小表示不同,这种方法用于给轮廓线上的联通情况确定一个... -
YbtOJ-方格填写【插头dp】
2022-02-05 19:56:31但是这样的状态也是平方的,我们需要考虑压缩一下状态,正常来说的插头 d p dp dp可能是 O ( 5 m ) O(5^m) O(5m)的状态,但是注意到每队网格只能连一条边,所以对于每个块最多只能剩下插头数的状态,也就是除了当且...