插头DP学习笔记——从入门到……（？？？）插头DP学习笔记——从入门到…

我们今天来学习插头DP？？？
BZOJ 2595：[Wc2008]游览计划
Input

第一行有两个整数，N和 M，描述方块的数目。
接下来 N行，每行有 M 个非负整数，如果该整数为 0，则该方块为一个景点；
否则表示控制该方块至少需要的志愿者数目。相邻的整数用（若干个）空格隔开，
行首行末也可能有多余的空格。

Output

由 N + 1行组成。第一行为一个整数，表示你所给出的方案
中安排的志愿者总数目。
接下来 N行，每行M 个字符，描述方案中相应方块的情况：
z ‘_’（下划线）表示该方块没有安排志愿者；
z ‘o’（小写英文字母o）表示该方块安排了志愿者；
z ‘x’（小写英文字母x）表示该方块是一个景点；
注：请注意输出格式要求，如果缺少某一行或者某一行的字符数目和要求不
一致（任何一行中，多余的空格都不允许出现），都可能导致该测试点不得分。

Sample Input

4 4
0 1 1 0
2 5 5 1
1 5 5 1
0 1 1 0

Sample Output

6
xoox
_o
_o
xoox

题解
我们可以不考虑括号表示法（像什么独立插头什么的），这道题我们考虑一下最小表示法
我们对于每个联通块标一个号，最后要求所有联通块在一起并且要求某些格子必须选，选格子有一定的价值，求最小价值
我们对于一个格子先判断选择和不选
有几种情况必须选
1.这个点是景点
2.这个点的上面有插头而这一个轮廓线上没有别的插头连通性和上面这个插头的连通性相同了
那么不选就直接把这个东西的插头改成0
然后选的话
如果上下都没有插头，新建一个连通块
如果左边有插头而上面没有插头，那么连通性从旁边过继过来
如果左边有插头上面也有插头，把这个轮廓线上所有的和左插头连通性相同的改成上插头的连通性
这个就是最小表示法啦！
代码

#include #include #include #include #include //#define ivorysi #define MOD 97171 using namespace std; typedef long long ll; struct node { int next,val,pre,pos,state; bool choose; }edge[1000005]; int sumedge; struct HashType { int head[MOD + 5],lastsum; void init() { memset(head,0,sizeof(head)); lastsum = sumedge + 1; } void Insert(const int &S,const int &cost,const int &pos,const int &pre,const bool &flag) { int x = S % MOD; for(int i = head[x] ; i ; i = edge[i].next) { if(edge[i].state == S) { if(cost < edge[i].val) { edge[i].val = cost; edge[i].pre = pre; edge[i].pos = pos; edge[i].choose = flag; } return ; } }edge[++sumedge].val = cost; edge[sumedge].state = S; edge[sumedge].pre = pre; edge[sumedge].pos = pos; edge[sumedge].choose = flag; edge[sumedge].state = S; head[x] = sumedge; } }cur,last; int n,m,mapv[15][15]; int conj[15],mp[10],ans,lastedge; bool g[15][15]; void decode(int state) { for(int i = m ; i >= 1 ; --i) { conj[i] = state & 7; state >>= 3; } } int encode() { int x = 0 , tot = 0; memset(mp,-1,sizeof(mp)); mp[0] = 0; for(int i = 1 ; i <= m ; ++i) { if(mp[conj[i]] == -1) mp[conj[i]] = ++tot; conj[i] = mp[conj[i]]; x = x << 3 | conj[i]; } return x; } void DP(int x,int y,int id) { decode(edge[id].state); int west = conj[y - 1]; int north = conj[y]; int nxt; bool flag; if(mapv[x][y] == 0) flag = 0; else if(!north) flag = 1; else { flag = 0; for(int i = 1 ; i <= m && !flag; ++i) { if(i != y && conj[i] == north) flag = 1; } } if(flag) { conj[y] = 0; nxt = encode(); cur.Insert(nxt,edge[id].val,(x - 1) * m + y,id,0); conj[y] = north; } if(!north && !west) conj[y] = 7; else if(!north && west > 0) conj[y] = west; else if(west > 0 && north > 0 && west !=north){ for(int i = 1; i <= y ; ++i) { if(conj[i] == west) conj[i] = north; } } nxt = encode(); cur.Insert(nxt,edge[id].val + mapv[x][y],(x - 1) * m + y ,id,1); } void Update(int id) { decode(edge[id].state); for(int i = 1 ; i <= m ; ++i) { if(conj[i] > 1) return; } if(edge[id].val < ans) { ans = edge[id].val; lastedge = id; } } void getans(int id) { if(id <= 0) return; int r = edge[id].pos; int l = (r - 1) / m + 1; r = (r - 1) % m + 1; g[l][r] = edge[id].choose; getans(edge[id].pre); } int main() { #ifdef ivorysi freopen("f1.in","r",stdin); #endif scanf("%d%d",&n,&m); ans = 0x7fffffff; for(int i = 1 ; i <= n ; ++i) { for(int j = 1 ; j <= m ; ++j) { scanf("%d",&mapv[i][j]); } } last.Insert(0,0,101,0,0); last.lastsum = 1; for(int i = 1 ; i <= n ; ++i) { for(int j = 1 ; j <= m ; ++j) { cur.init(); for(int k = sumedge ; k >= last.lastsum ; --k) { DP(i,j,k); } last = cur; } } for(int k = sumedge ; k >= last.lastsum ; --k) { Update(k); } printf("%d\n",ans); getans(lastedge); for(int i = 1 ; i <= n ; ++i) { for(int j = 1 ; j <= m ; ++j) { if(mapv[i][j] == 0) putchar('x'); else if(g[i][j]) putchar('o'); else putchar('_'); } putchar('\n'); } }

BZOJ 1187: [HNOI2007]神奇游乐园

Time Limit: 10 Sec Memory Limit: 162 MB
Submit: 1280 Solved: 687
[Submit][Status][Discuss]

Description

经历了一段艰辛的旅程后，主人公小P乘坐飞艇返回。在返回的途中，小P发现在漫无边际的沙漠中，有一块狭长的绿地特别显眼。往下仔细一看，才发现这是一个游乐场，专为旅途中疲惫的人设计。娱乐场可以看成是一块大小为n×m的区域，且这个n×m的区域被分成n×m个小格子，每个小格子中就有一个娱乐项目。然而，小P并不喜欢其中的所有娱乐项目，于是，他给每个项目一个满意度。满意度为正时表示小P喜欢这个项目，值越大表示越喜欢。为负时表示他不喜欢，这个负数的绝对值越大表示他越不喜欢。为0时表示他对这个项目没有喜恶。小P决定将飞艇停在某个小格中，然后每步他可以移动到相邻的上下左右四个格子的某个格子中。小P希望找一条路径，从飞艇所在格出发，最后又回到这个格子。小P有一个习惯，从不喜欢浪费时间。因此，他希望经过每个格子都是有意义的：他到一个地方后，就一定要感受以下那里的惊险和刺激，不管自己是不是喜欢那里的娱乐项目。而且，除了飞艇所在格，其他的格子他不愿意经过两次。小P希望自己至少要经过四个格子。在满足这些条件的情况下，小P希望自己玩过的娱乐项目的满意度之和最高。你能帮他找到这个最高的满意度之和吗？

Input

输入文件中的第一行为两个正整数n和m，表示游乐场的大小为n×m。因为这个娱乐场很狭窄，所以n和m满足：2<=n<=100，2<=m<=6。接下来的n行，每行有m个整数，第i行第j列表示游乐场的第i行第j列的小格子中的娱乐项目的满意度，这个满意度的范围是[-1000，1000]。同一行的两个整数之间用空格隔开。

Output

输出文件中仅一行为一个整数，表示最高的满意度之和。

Sample Input

4 4
100 300 -400 400
-100 1000 1000 1000
-100 -100 -100 -100
-100 -100 -100 1000

Sample Output

4000

HINT

大家测下这个数据 5 5 1 1 -100 3 3 1 1 -100 3 3 1 1 -100 3 3 1 1 -100 3 3 1 1 -100 3 3 结果是30?

题解
我们来学习括号表示法！
由于一条回路有很多路径拼在一起的，一条路径的左右端点对应一对左右括号
那么一个轮廓线就可以用括号表示
我们分类讨论
我们设上插头为north，左插头为west
设无插头是0，左括号是1，右括号是2
如果north == west == 0
那么我们可以选择跳过这个点
或者新建一个插头，向下延伸的插头是1，向右延伸的插头是2
如果north == west == 1
那么我们连上这个这个格子，然后找到上格子对应的右括号，把它改成左括号
如果north == west == 2
情况和上一个类似
如果north 和 west其中有一个是0，另一个不为0
那么我们可以把有插头的那个格子转移到下边或者右边
如果north == 1 west ==2
我们连上这个地方，然后直接改成无插头，因为这两个路径合并成了一条路径
如果north == 2 west == 1
我们连上，这就构成了一条回路，我们修改成无插头，同时更新答案，这个状态不加入哈希表
代码

#include #include #include #include #include //#define ivorysi #define MOD 97171 using namespace std; typedef long long ll; struct node { int next,val,state; }; struct HashType { int head[MOD + 5],sumedge; node edge[1000005]; void Init() { memset(head,0,sizeof(head)); sumedge = 0; } void Insert(const int &S,const int &cost) { int x = S % MOD; for(int i = head[x] ; i ; i = edge[i].next) { if(edge[i].state == S) { if(cost > edge[i].val) { edge[i].val = cost; } return ; } } edge[++sumedge].val = cost; edge[sumedge].state = S; edge[sumedge].next = head[x]; head[x] = sumedge; } }*cur,*last; int conj[10],n,m; int mapv[105][15],ans; void decode(int state) { for(int i = m ; i >= 0 ; --i) { conj[i] = state & 3; state >>= 2; } } int encode() { int x = 0; for(int i = 0 ; i <= m ; ++i) { x = x << 2 | conj[i]; } return x; } void DP(int x,int y,int S,int V) { decode(S); int north = conj[y]; int west = conj[y - 1]; int nxt; if(!west && !north) { nxt = encode(); if(y == m) nxt >>= 2; cur->Insert(nxt,V); conj[y] = 2; conj[y - 1] = 1; nxt = encode(); if(y == m)return; cur->Insert(nxt,V + mapv[x][y]); } if(west == 2 && north == 1) { conj[y] = conj[y - 1] = 0; nxt = encode(); if(y == m) nxt >>= 2; cur->Insert(nxt,V + mapv[x][y]); } if(west == 1 && north == 1) { conj[y] = conj[y - 1] = 0; int top = 0; for(int h = y ; h <= m ; ++h) { if(conj[h] == 1) --top; else if(conj[h] == 2) ++top; if(top == 1) { conj[h] = 1; nxt = encode(); if(y == m) nxt >>= 2; cur->Insert(nxt,V + mapv[x][y]); break; } } } if(west == 2 && north == 2) { conj[y] = conj[y - 1] = 0; int top = 0; for(int h = y ; h >= 1 ; --h) { if(conj[h] == 1) ++top; else if(conj[h] == 2) --top; if(top == 1) { conj[h] = 2; nxt = encode(); if(y == m) nxt >>= 2; cur->Insert(nxt,V + mapv[x][y]); break; } } } if((west == 0 || north == 0) && north + west != 0) { int w = north + west; if(y == m) { conj[m - 1] = w; conj[m] = 0; nxt = encode(); nxt >>= 2; cur->Insert(nxt,V + mapv[x][y]); return; } nxt = encode(); cur->Insert(nxt,V + mapv[x][y]); swap(conj[y],conj[y - 1]); nxt = encode(); cur->Insert(nxt,V + mapv[x][y]); } if(west == 1 && north == 2) { conj[y] = conj[y - 1] = 0; nxt = encode(); if(y == m) nxt >>= 2; if(nxt == 0) { ans = max(ans,V + mapv[x][y]); } } } int main() { #ifdef ivorysi freopen("f1.in","r",stdin); #endif scanf("%d%d",&n,&m); for(int i = 1 ; i <= n ; ++i) { for(int j = 1 ; j <= m ; ++j) { scanf("%d",&mapv[i][j]); } } last = new HashType; cur = new HashType; last->Insert(0,0); ans = -100000000; for(int i = 1 ; i <= n ; ++i) { for(int j = 1 ; j <= m ; ++j) { cur->Init(); for(int k = last->sumedge ; k >= 1 ; --k) { DP(i,j,last->edge[k].state,last->edge[k].val); } swap(last,cur); } } printf("%d\n",ans); }

Ural 1519. Formula 1

Time limit: 1.0 second
Memory limit: 64 MB

Background

Regardless of the fact, that Vologda could not get rights to hold the Winter Olympic games of 20**, it is well-known, that the city will conduct one of the Formula 1 events. Surely, for such an important thing a new race circuit should be built as well as hotels, restaurants, international airport - everything for Formula 1 fans, who will flood the city soon. But when all the hotels and a half of the restaurants were built, it appeared, that at the site for the future circuit a lot of gophers lived in their holes. Since we like animals very much, ecologists will never allow to build the race circuit over the holes. So now the mayor is sitting sadly in his office and looking at the map of the circuit with all the holes plotted on it.

Problem

Who will be smart enough to draw a plan of the circuit and keep the city from inevitable disgrace? Of course, only true professionals - battle-hardened programmers from the first team of local technical university!.. But our heroes were not looking for easy life and set much more difficult problem: "Certainly, our mayor will be glad, if we find how many ways of building the circuit are there!" - they said.
It should be said, that the circuit in Vologda is going to be rather simple. It will be a rectangle N*M cells in size with a single circuit segment built through each cell. Each segment should be parallel to one of rectangle's sides, so only right-angled bends may be on the circuit. At the picture below two samples are given for N = M = 4 (gray squares mean gopher holes, and the bold black line means the race circuit). There are no other ways to build the circuit here.
[00e95cac-20da-4b1b-b502-28cb9f561a1d.png][3]

Input

The first line contains the integer numbers N and M (2 ≤ N, M ≤ 12). Each of the next N lines contains M characters, which are the corresponding cells of the rectangle. Character "." (full stop) means a cell, where a segment of the race circuit should be built, and character "*" (asterisk) - a cell, where a gopher hole is located. There are at least 4 cells without gopher holes.

Output

You should output the desired number of ways. It is guaranteed, that it does not exceed 263-1.

Samples
input
4 4
**..
....
....
....
output

2

input

4 4
....
....
....
....

output

6

题解
求一个有障碍图的哈密顿回路方案数
和上一道题思路差不多，只不过不能有格不选，有障碍的格子必须上下都是0
代码

#include #include #include #include #include //#define ivorysi #define MOD 97171 using namespace std; typedef long long ll; struct node { int next,state; ll val; }; struct HashType { int head[MOD + 5],sumedge; node edge[2000005]; void Init() { memset(head,0,sizeof(head)); sumedge = 0; } void Insert(const int &S,const ll &cost) { int x = S % MOD; for(int i = head[x] ; i ; i = edge[i].next) { if(edge[i].state == S) { edge[i].val += cost; return ; } } edge[++sumedge].state = S; edge[sumedge].val = cost; edge[sumedge].next = head[x]; head[x] = sumedge; } }*cur,*last; int conj[15],n,m,ux,uy; ll ans; char mapv[15][15]; void decode(int state) { for(int i = m ; i >= 0 ; --i) { conj[i] = state & 3; state >>= 2; } } int encode() { int x = 0; for(int i = 0 ; i <= m ; ++i) { x = x << 2 | conj[i]; } return x; } void DP(int x,int y,int S,ll V) { decode(S); int north = conj[y]; int west = conj[y - 1]; int nxt; if(mapv[x][y] == '*') { if(!west && !north) { conj[y] = conj[y - 1] = 0; nxt = encode(); if(y == m) nxt >>= 2; cur->Insert(nxt,V); } return ; } if(!west && !north) { conj[y] = 2; conj[y - 1] = 1; nxt = encode(); if(y == m)return; cur->Insert(nxt,V); } if(west == 2 && north == 1) { conj[y] = conj[y - 1] = 0; nxt = encode(); if(y == m) nxt >>= 2; cur->Insert(nxt,V); } if(west == 1 && north == 1) { conj[y] = conj[y - 1] = 0; int top = 0; for(int h = y ; h <= m ; ++h) { if(conj[h] == 1) --top; else if(conj[h] == 2) ++top; if(top == 1) { conj[h] = 1; nxt = encode(); if(y == m) nxt >>= 2; cur->Insert(nxt,V); break; } } } if(west == 2 && north == 2) { conj[y] = conj[y - 1] = 0; int top = 0; for(int h = y ; h >= 1 ; --h) { if(conj[h] == 1) ++top; else if(conj[h] == 2) --top; if(top == 1) { conj[h] = 2; nxt = encode(); if(y == m) nxt >>= 2; cur->Insert(nxt,V); break; } } } if((west == 0 || north == 0) && north + west != 0) { int w = north + west; if(y == m) { conj[m - 1] = w; conj[m] = 0; nxt = encode(); nxt >>= 2; cur->Insert(nxt,V); return; } nxt = encode(); cur->Insert(nxt,V); swap(conj[y],conj[y - 1]); nxt = encode(); cur->Insert(nxt,V); } if(west == 1 && north == 2) { conj[y] = conj[y - 1] = 0; nxt = encode(); if(nxt == 0 && x == ux && y == uy) ans += V; } } int main() { #ifdef ivorysi freopen("f1.in","r",stdin); #endif scanf("%d%d",&n,&m); for(int i = 1 ; i <= n ; ++i) { scanf("%s",mapv[i] + 1); for(int j = 1 ; j <= m ; ++j) { if(mapv[i][j] != '*') { ux = i; uy = j; } } } last = new HashType; cur = new HashType; last->Insert(0,1); for(int i = 1 ; i <= n ; ++i) { for(int j = 1 ; j <= m ; ++j) { cur->Init(); for(int k = last->sumedge ; k >= 1 ; --k) { DP(i,j,last->edge[k].state,last->edge[k].val); } swap(last,cur); } } printf("%lld\n",ans); }

BZOJ 2331: [SCOI2011]地板

Time Limit: 5 Sec Memory Limit: 128 MB
Submit: 1403 Solved: 589
[Submit][Status][Discuss]

Description

lxhgww的小名叫“小L”，这是因为他总是很喜欢L型的东西。小L家的客厅是一个矩形，现在他想用L型的地板来铺满整个客厅，客厅里有些位置有柱子，不能铺地板。现在小L想知道，用L型的地板铺满整个客厅有多少种不同的方案？
需要注意的是，如下图所示，L型地板的两端长度可以任意变化，但不能长度为0。铺设完成后，客厅里面所有没有柱子的地方都必须铺上地板，但同一个地方不能被铺多次。
[22.jpg.gif][4]

Input

输入的第一行包含两个整数，R和C，表示客厅的大小。
接着是R行，每行C个字符。’_’表示对应的位置是空的，必须铺地板；’*’表示对应的位置有柱子，不能铺地板。

Output

输出一行，包含一个整数，表示铺满整个客厅的方案数。由于这个数可能很大，只需输出它除以20110520的余数。

Sample Input

2 2
*_
__

Sample Output

1

HINT

R*C<=100

题解
把R < C打成R > C我是真的瞎……
数组开成10 10的真的是折翼……
好了说说题解吧
这道题的插头和往常的路径题不太一样，我们重新设置一下插头
0 表示没有插头
1 是这个方向上需要延伸一个格子，但是还没有转弯
2 表示这个方向上需要延伸一个格子，但是转过弯了
然后转移，首先我们可以判断，上插头和左插头如果都有数字，且都不为1，那么一定不合法，这个状态就可以跳过
然后如果上插头和左插头为0，这个格子又不是障碍物，那么我们就新建一个
可以把这个格子向下的影响设成1，这就新建了一个_| 或者 L型地板的上半部分
或者向右的影响设成1，那么就新建了一个-|型的上半臂
向下和向右的影响都是2，那么就已经转弯了|-就是这样形状的一个角
如果上插头是1，左插头是0
那么可以上插头继续向下延伸或者转弯
如果上插头是0，左插头是1
和上面的情况类似
如果上插头是2，左插头是0
那么可以继续向下延伸，或者结束这个地板
如果上插头是0，左插头是2
和上面的情况类似
如果上插头是1，左插头是1
注意到_|型地板并不能设置向左的转弯，在这种情况里，我们会合并两个分支的地板，来转移这种形状的地板
代码

#include #include #include #include #define MOD 97171 #define mod 20110520 //#define ivorysi using namespace std; typedef long long ll; int R,C; char s[105][105],mapv[105][105]; struct node { int next,state; ll val; }; struct HashType { int head[MOD + 5],sumedge; node edge[1000005]; void Init() { memset(head,0,sizeof(head)); sumedge = 0; } void Insert(const int &S,const ll &val) { int x = S % MOD; for(int i = head[x] ; i ; i = edge[i].next) { if(edge[i].state == S) { edge[i].val += val; edge[i].val %= mod; return ; } } edge[++sumedge].val = val; edge[sumedge].state = S; edge[sumedge].next = head[x]; head[x] = sumedge; }}*last,*cur; int conj[15]; ll ans; void decode(int state) { for(int i = C ; i >= 0 ; --i) { conj[i] = state & 3; state >>= 2; } } int encode() { int x = 0; for(int i = 0 ; i <= C ; ++i) { x = (x << 2) | conj[i]; } return x; } void DP(int x,int y,int S,ll V) { decode(S); int north = conj[y]; int west = conj[y - 1]; int nxt; if(mapv[x][y] == '*') { if(north == 0 && west == 0) { nxt = encode(); if(y == C) nxt >>= 2; cur->Insert(nxt,V); } return; } if(north == 0 && west == 0) { conj[y - 1] = 1; conj[y] = 0; nxt = encode(); if(y == C) nxt >>= 2; cur->Insert(nxt,V); conj[y - 1] = 2; conj[y] = 2; if(y != C) nxt = encode() , cur->Insert(nxt,V); conj[y] = 1; conj[y - 1] = 0; if(y != C) nxt = encode() , cur->Insert(nxt,V); } if(north == 1 && west == 0) { conj[y - 1] = 1; conj[y] = 0; nxt = encode() ; if(y == C) nxt >>= 2; cur->Insert(nxt,V); conj[y - 1] = 0; conj[y] = 2; if(y != C)nxt = encode() , cur->Insert(nxt,V); } if(north == 2 && west == 0) { conj[y - 1] = 2; conj[y] = 0; nxt = encode(); if(y == C) nxt >>= 2; cur->Insert(nxt,V); conj[y - 1] = 0; conj[y] = 0; nxt = encode(); if(y == C) nxt >>= 2; cur->Insert(nxt,V); } if(north == 0 && west == 1) { conj[y - 1] = 0; conj[y] = 1; if(y != C) nxt = encode() , cur->Insert(nxt,V); conj[y - 1] = 2; conj[y] = 0; nxt = encode(); if(y == C) nxt >>= 2; cur->Insert(nxt,V); } if(north == 0 && west == 2) { conj[y - 1] = 0; conj[y] = 2; if(y != C) nxt = encode() , cur->Insert(nxt,V); conj[y - 1] = 0; conj[y] = 0; nxt = encode(); if(y == C) nxt >>= 2; cur->Insert(nxt,V); } if(north == 1 && west == 1){ conj[y - 1] = 0; conj[y] = 0; nxt = encode(); if(y == C) nxt >>= 2; cur->Insert(nxt,V); } } int main() { #ifdef ivorysi freopen("f1.in","r",stdin); #endif scanf("%d%d",&R,&C); for(int i = 1 ; i <= R ; ++i) { scanf("%s",s[i] + 1); } if(R < C) { for(int i = 1 ; i <= R ; ++i) { for(int j = 1 ; j <= C ; ++j) { mapv[j][i] = s[i][j]; } } swap(R,C); } else { for(int i = 1 ; i <= R ; ++i) { for(int j = 1 ; j <= C ; ++j ){ mapv[i][j] = s[i][j]; } } } last = new HashType; cur = new HashType; last->Insert(0,1); for(int i = 1 ; i <= R ; ++i) { for(int j = 1 ; j <= C ; ++j) { cur->Init(); for(int k = last->sumedge ; k >= 1 ; --k) { DP(i,j,last->edge[k].state,last->edge[k].val); } swap(last,cur); } } for(int k = last->sumedge ; k >= 1 ; --k) { int S = last->edge[k].state; ll V = last->edge[k].val; if(S == 0) {ans += V; ans %= mod; } } printf("%lld\n",ans); }

【插头DP学习笔记——从入门到……（？？？）】转载于:https://www.cnblogs.com/ivorysi/p/9058111.html