关键词：
[URAL1519]Formula 1
试题描述
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.
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 imes 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.
一个 (N imes M)（$ le 12$）的棋盘，有的格子存在障碍，求经过所有非障碍格子的哈密顿回路个数。
输入
The first line contains the integer numbers (N) and (M) ((2 le N, M le 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.
输出
You should output the desired number of ways. It is guaranteed, that it does not exceed (2^{63}-1).
输入示例1
4 4
**..
....
....
....输出示例1
2输入示例2
4 4
....
....
....
....输出示例2
6数据规模及约定
对于 100% 的数据，(0 < c_i le p le 10); (0 < u_i,v_i,d_i le n le 1000); (0 le m le 3000); (0 le w_i le 20000)。
题解
裸的轮廓线 dp，练练括号序列表示法。
注意这题的坑，比如开 long long，最后连成的必须是一个连通分量等。
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cctype>
#include <algorithm>
using namespace std;
#define rep(i, s, t) for(int i = (s); i <= (t); i++)
#define dwn(i, s, t) for(int i = (s); i >= (t); i--)
int read() {
int x = 0, f = 1; char c = getchar();
while(!isdigit(c)){ if(c == ‘-‘) f = -1; c = getchar(); }
while(isdigit(c)){ x = x * 10 + c - ‘0‘; c = getchar(); }
return x * f;
}
#define maxn 16
#define maxs 1594333
#define LL long long
int n, m;
LL f[2][maxs];
bool islst[maxn][maxn];
char Map[maxn][maxn];
void encode(int& s, int A[]) {
s = 0;
dwn(i, m + 1, 1) s = s * 3 + A[i];
return ;
}
void decode(int A[], int s) {
rep(i, 1, m + 1) A[i] = s % 3, s /= 3;
return ;
}
int main() {
n = read(); m = read();
rep(i, 1, n) scanf("%s", Map[i] + 1);
dwn(i, n, 1) {
bool has = 0;
dwn(j, m, 1) if(Map[i][j] == ‘.‘){ has = islst[i][j] = 1; break; }
if(has) break;
}
int all = 1, cur = 0, A[maxn], half[maxn], S[maxn], top;
rep(i, 1, m + 1) all *= 3; all--;
f[cur][0] = 1;
rep(i, 1, n) rep(j, 1, m) {
memset(f[cur^1], 0, sizeof(f[cur^1]));
rep(s, 0, all) if(f[cur][s]) {
decode(A, s);
// printf("f[(%d, %d)][", i, j); rep(k, 1, m + 1) printf("%d%c", A[k], k < m + 1 ? ‘ ‘ : ‘]‘); printf(" = %d
", f[cur][s]);
top = 0;
rep(k, 1, m + 1) {
if(A[k] == 1) S[++top] = k;
if(A[k] == 2) half[S[top]] = k, half[k] = S[top--];
}
int ts;
if((A[j] || A[j+1]) && Map[i][j] == ‘*‘) continue;
if(j < m) {
if(A[j] && A[j+1]) {
int a = half[j], b = half[j+1]; if(a > b) swap(a, b);
if(A[j] == 1 && A[j+1] == 2 && !islst[i][j]) continue;
A[a] = 1; A[b] = 2;
A[j] = A[j+1] = 0;
encode(ts, A);
f[cur^1][ts] += f[cur][s];
}
else if(A[j]) {
A[j] = 3 - A[half[j]];
encode(ts, A);
f[cur^1][ts] += f[cur][s];
A[j] = 0;
A[j+1] = 3 - A[half[j]];
encode(ts, A);
f[cur^1][ts] += f[cur][s];
}
else if(A[j+1]) {
A[j+1] = 3 - A[half[j+1]];
encode(ts, A);
f[cur^1][ts] += f[cur][s];
A[j+1] = 0;
A[j] = 3 - A[half[j+1]];
encode(ts, A);
f[cur^1][ts] += f[cur][s];
}
else {
if(Map[i][j] == ‘*‘) f[cur^1][s] += f[cur][s];
else A[j] = 1, A[j+1] = 2, encode(ts, A), f[cur^1][ts] += f[cur][s];
}
}
else {
if(A[j] && A[j+1]) {
int a = half[j], b = half[j+1]; if(a > b) swap(a, b);
if(A[j] == 1 && A[j+1] == 2 && !islst[i][j]) continue;
A[a] = 1; A[b] = 2;
A[j] = A[j+1] = 0;
dwn(k, m + 1, 2) A[k] = A[k-1]; A[1] = 0;
encode(ts, A);
f[cur^1][ts] += f[cur][s];
}
else if(A[j]) {
A[j] = 3 - A[half[j]];
dwn(k, m + 1, 2) A[k] = A[k-1]; A[1] = 0;
encode(ts, A);
f[cur^1][ts] += f[cur][s];
}
else if(A[j+1]) {
A[j+1] = 0;
A[j] = 3 - A[half[j+1]];
dwn(k, m + 1, 2) A[k] = A[k-1]; A[1] = 0;
encode(ts, A);
f[cur^1][ts] += f[cur][s];
}
else if(Map[i][j] == ‘*‘) {
dwn(k, m + 1, 2) A[k] = A[k-1]; A[1] = 0;
encode(ts, A);
f[cur^1][ts] += f[cur][s];
}
}
}
cur ^= 1;
}
printf("%lld
", f[cur][0]);
return 0;
}ural1519formula1(dp)
题意：给定一个n*m的矩阵，问你能花出多少条回路。#pragmacomment(linker,"/STACK:1024000000,1024000000")#include<cstdio>#include<string>#include<cstdlib>#include<cmath>#include<iostream>#include&l 查看详情
ural1519formula1
【算法】插头DP【题解】【算法】动态规划基于连通性状态压缩的动态规划问题 论文题http://www.cnblogs.com/kuangbin/ 题解+代码1.注意换行处理2.在最后一格时向右向下都没有路，而向右和向下的状态是需要判定有没有路的，所... 查看详情
bzoj1814ural1519formula1插头dp
题目描述一个m*n的棋盘,有的格子存在障碍,求经过所有非障碍格子的哈密顿回路个数。输入ThefirstlinecontainstheintegernumbersNandM(2≤N,M≤12).EachofthenextNlinescontainsMcharacters,whicharethecorrespondingcellsoftherectangle.Character"."(fu 查看详情
bzoj1814ural1519formula1插头dp
【BZOJ1814】Ural1519Formula1题意：一个m*n的棋盘,有的格子存在障碍,求经过所有非障碍格子的哈密顿回路个数。(n,m<=12)题解：插头DP板子题，刷板子，附带题解链接。如何存放状态呢？可以采用hash，我们的hash表形如一个队列，每次... 查看详情
bzoj1814:ural1519formula1动态规划插头dp(代码片段)
dbzoj依然爆炸题目描述一个m*n的棋盘,有的格子存在障碍,求经过所有非障碍格子的哈密顿回路个数。输入ThefirstlinecontainstheintegernumbersNandM(2≤N,M≤12).EachofthenextNlinescontainsMcharacters,whicharethecorrespondingcellsoftherectangle.Character"." 查看详情
[ural1519]formula1轮廓线dp括号序列
题意 n*m的矩形,有坏点,问哈密顿回路数量. n,m<=11. 分析1. 确立状态 我们考虑轮廓线DP. 为此,我们要刻画并量化轮廓线的相关信息: ①插头是否存在? ②插头的连通性. 我们发现:插头一一对... 查看详情
bzoj1814:ural1519formula1插头dp经典题
用的括号序列，听说比较快。 然并不会预处理，只会每回暴力找匹配的括号。 1#include<iostream>2#include<cstdio>3#include<cstring>4#include<algorithm>5#defineN1999176#definelllonglong7#definebp1<<bit[j-1]8# 查看详情
[ural1519]formula1[插头dp入门](代码片段)
题面：传送门思路：先理解一下题意：实际上就是要你求这个棋盘中的哈密顿回路个数，障碍不能走看到这个数据范围，还有回路处理，就想到使用插头dp来做了观察一下发现，这道题因为都是回路，所以联通块上方的插头一定... 查看详情
bzoj1814:ural1519formula1插头dp(代码片段)
设f[i][j][s]为轮廓线推到格子(i,j)，状态为s的方案数括号表示一段线的左端和右端，表示成左括号和右括号，状压的时候用1和2表示，0表示已经闭合下面的蓝线是黄色格子的轮廓线，dp转移要把它转到橙色轮廓线，设已经在状压的... 查看详情
放假之前
咸鱼好久啦。快放假了调整下。圣诞打到了小礼物自己动手丰衣足食（其实是没人给我送）12.24URAL1519 Formula1插头dp。抄板子。1#include<iostream>2#include<cstdio>3#include<cstring>4#include<algorithm>5usingnamespacestd;6typede 查看详情
插头dp题表（已完成）
bzoj1814:Ural1519Formula1 bzoj3125:CITY bzoj1210:[HNOI2004]邮递员 bzoj2331:[SCOI2011]地板 bzoj1187:[HNOI2007]神奇游乐园 bzoj2310:ParkII 查看详情
[bzoj]|[ura]formula1-----插头dp入门
1519.Formula1Timelimit:1.0secondMemorylimit:64MBBackgroundRegardlessofthefact,thatVologdacouldnotgetrightstoholdtheWinterOlympicgamesof20**,itiswell-known,thatthecitywillconductoneoftheFormula1events. 查看详情
补题清单
HDU3585 HDU1693 URAL1519 FZU1977 HDU1964 HDU3377 POJ1739 POJ3133 BZOJ1025 HDU4285 专题710031004100510061008 查看详情
ural-1901spaceelevators
题目：NowadaysspaceshipsareneverlaunchedfromtheEarth‘ssurface.ThereisahugespaceportplacedinthegeostationaryorbitandconnectedtotheEarthwithcarbonnanotubecables.Peopleandcargoaredeliveredtotheorbitbyelevat 查看详情
ural2089experiencedcoachtwosat
DescriptionMishatrainsseveralACMteamsattheuniversity.Heisanexperiencedcoach,andhedoesnotunderestimatethemeaningoffriendlyandcollaborativeatmosphereduringtrainingsessions.Itusedtobethatway,butoneofthet 查看详情
ural2020trafficjaminflowertown
2020.TrafficJaminFlowerTownTimelimit:1.0secondMemorylimit:64MBHavingreturnedfromSunCity,Dunnotoldallhisfriendsthateveryshortymayhaveapersonalautomobile.Immediatelyafterthatsomanycitizenstookafancyofbe 查看详情
ural1424minibus
MinibusTimelimit:1.0secondMemorylimit:64MBBackgroundMinibusdriverSergeyA.Greedsonhasbecometotallyfamousforhisphenomenalgreediness.Heclaimedtimeandagainthatheheldhimselfinreadinesstothrottlehisbrothera 查看详情
ural1855tradeguildsoferathia
TradeGuildsofErathiaTimelimit:2.0secondMemorylimit:64MBThecontinentofAntagarichwascolonizedslowly.LongagoitsnorthernpartwasinhabitedbytheelvesofAvlee.Later,thehotsoutherndesertofBracadawasoccupiedbyth 查看详情