搜索题目 专项题解
P4206 [NOI2005] 聪聪与可可
题意简述
给定无向图，以及聪聪和可可的初始位置。
聪聪要抓可可，聪聪先走，可可后走。聪聪一个单位时间内可以走一到两步，每次都是选择最靠近可可的点走，如果有多个距离可可相同的点则选择标号最小的。
可可单位时间只能走一步，并且等概率的选择附近相邻的点或者呆在原地不动。
问平均聪聪走多少个单位时间可以追到可可。
解题报告
考虑爆搜改记搜。
爆搜：需要记住当前聪聪的位置、可可的位置，每次枚举可可下一步走哪（也可以不走），然后让聪聪走两步，继续搜索（此处需要预处理聪聪应该往哪走）。退出条件是聪聪和可可重合 / 一步抓到 / 两步抓到。
改记搜：模板记搜，直接存状态 dp[i][j] 表示聪聪在 i 点，可可在 j 点的期望步数。
预处理跑 n 遍 bfs 得到任意两点间距离即可。
代码实现
// memsearch
const int MAXN = 1000 + 10;
int n, e, c, m;
int sdis[MAXN][MAXN];
int nxtnode[MAXN][MAXN]; // i -> j 最短路要走的下一个点
std::vector<int> G[MAXN];
void bfs(int st, int *dist) {
static bool vis[MAXN];
memset(vis, 0, sizeof vis);
std::queue<int> q; q.push(st); dist[st] = 0; vis[st] = true;
while (!q.empty()) {
int u = q.front(); q.pop();
vis[u] = false;
forall (G[u], i) {
int v = G[u][i];
if (dist[v] > dist[u] + 1) {
dist[v] = dist[u] + 1;
if (!vis[v]) { q.push(v); vis[v] = true; }
}
}
}
}
double dp[MAXN][MAXN];
double search(int cat, int mouse) {
if (dp[cat][mouse] != 0) return dp[cat][mouse];
double &ans = dp[cat][mouse];
if (cat == mouse) return ans = 0;
if (nxtnode[cat][mouse] == mouse) return ans = 1;
if (nxtnode[nxtnode[cat][mouse]][mouse] == mouse) return ans = 1;
forall (G[mouse], i) {
int nv = G[mouse][i];
ans += search(nxtnode[nxtnode[cat][mouse]][mouse], nv) + 1;
} ans = (ans + 1 + search(nxtnode[nxtnode[cat][mouse]][mouse], mouse)) / (double) (G[mouse].size() + 1); //不走的情况
// 也可以写成
// ans += search(nxtnode[nxtnode[cat][mouse]][mouse], nv);
// ans = (ans + search(nxtnode[nxtnode[cat][mouse]][mouse], mouse)) / (double) (G[mouse].size() + 1) + 1
// 区别就在于把循环里的 +1 拿出来
return ans;
}
int main() {
std::ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
cin >> n >> e >> c >> m;
rep (i, 1, e) {
int u, v; cin >> u >> v;
G[u].push_back(v); G[v].push_back(u);
}
memset(sdis, 0x3f, sizeof sdis);
rep (i, 1, n) bfs(i, sdis[i]);
memset(nxtnode, 0x3f, sizeof nxtnode);
for (int u = 1; u <= n; ++u) {
forall (G[u], i) {
int v = G[u][i];
for (int d = 1; d <= n; ++d) {
if (u == d) continue;
if (sdis[u][d] == sdis[v][d] + 1) {
nxtnode[u][d] = std::min(nxtnode[u][d], v);
}
}
}
}
cout << std::fixed << std::setprecision(3) << search(c, m) << endl;
return 0;
}
P3205 [HNOI2010]合唱队
题意简述
imp
解题报告
手玩发现，原序列中最后一个人会到理想队伍的1位置或者n位置，倒数第二个会到2或n-1
于是设 f[l][r][0/1] 表示理想队伍 [l,r] 中的人还没有确定原序列位置的原序列方案数，且当前放置的人是 l(0)还是r(1)
转移就看看当前人和上一个人是往哪放的
代码实现
const int MAXN = 1000 + 10;
const int HA = 19650827;
int n;
int aa[MAXN];
int f[MAXN][MAXN][2];
// 设 `f[l][r][0/1]` 表示理想队伍 `[l,r]` 中的人还没有确定原序列位置的原序列方案数
// 且本次放置的人是 `l(0)` 还是 `r(1)`
int search(int l, int r, int p) {
// [^v.........v^]
// 当前插入^，上次插入v
if (f[l][r][p] != -1) return f[l][r][p];
int &ans = f[l][r][p] = 0;
if (l == r) return ans = 1;
if (l + 1 == r) return ans = (aa[l] < aa[r]);
if (p == 0) {
// [^v.........]
if (aa[l] < aa[l + 1]) ans += search(l + 1, r, 0);
// [^.........v]
if (aa[l] < aa[r]) ans += search(l + 1, r, 1);
} else {
// [v.........^]
if (aa[r] > aa[l]) ans += search(l, r - 1, 0);
// [.........v^]
if (aa[r] > aa[r - 1]) ans += search(l, r - 1, 1);
} ans %= HA;
return ans;
}
int main() {
std::ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
cin >> n;
rep (i, 1, n) cin >> aa[i];
memset(f, -1, sizeof f);
cout << (search(1, n, 0) + search(1, n, 1)) % HA << endl;
return 0;
}
P2473 [SCOI2008] 奖励关
题意简述
k 次发钱，有 n 种金额（正数发钱，负数扣钱），每次等概率选一种金额发钱，可以拿也可以不拿。每种金额都有依赖，即拿一些金额必须之前拿过特定的金额。求期望最大钱数。
解题报告
一个长得比较像爆搜的记搜。
状态：当前发了 k 次，拿钱的状态如何（状压）
转移：枚举当前发哪种钱
代码实现
把数组开大了才过。。
const int MAXK = 1000 + 10;
const int MAXN = 17;
int k, n;
double aa[MAXN]; int pre[MAXN];
double dp[MAXK][(1 << MAXN) + 10];
bool vis[MAXK][(1 << MAXN) + 10];
double search(int tm, int stat) {
if (tm == k + 1) return 0;
if (vis[tm][stat]) return dp[tm][stat];
double &ans = dp[tm][stat]; vis[tm][stat] = true;
for (int i = 1; i <= n; ++i) {
if ((stat & pre[i]) == pre[i]) ans += std::max(search(tm + 1, stat | (1 << (i - 1))) + aa[i], search(tm + 1, stat)) / (double) n;
else ans += search(tm + 1, stat) / (double) n;
}
return ans;
}
int main() {
k = read(); n = read();
for (int i = 1; i <= n; ++i) {
aa[i] = read(); int fx = read();
while (fx != 0) {
pre[i] |= (1 << (fx - 1));
fx = read();
}
}
printf("%0.6lf", search(1, 0));
return 0;
}