Luogu 3638 [APIO 2013] 机器人

传送门

思路

   n n 这么小，会不会是搜索题？稍有经验的我直接否定了这个结论 = =。仔细读题并分析样例，发现原来一个位置可以有多个机器人，且机器人行走的时候无视其它机器人，那这个就是一张图啊。可以将这张图预处理出来，则问题变为把所有机器人在某个结点合并的路径长度之和的最小值。

  我本以为跑个多源 BFS 就好了，但是猛然发现机器人合并后步数会改变，然后我就凉了……

正解

  还是先将整张图预处理出来，注意需要用 DFS 记忆化保证时间复杂度。

  这道题其实是一个动态规划（怎么想到的 = =）。我们设 fl,r,x,yfl,r,x,y 表示使得 l∼r l ∼ r 的复合机器人在 (x,y) ( x , y ) 的最小代价，显然边界条件为：

  考虑转移。显然我们可以选择走一步：

  对于一个位置，我们先用第一个转移计算出自己的最小代价，再用第二个转移去更新别人的最小代价。发现，这个转移的方法与斯坦纳树的做法是十分类似的，但是和斯坦纳树本身毛关系都没有。

  是个铲铲！

参考代码

  唉，我太弱了，什么都不会，DFS 一开始写错了，调了一个上午……

（C++ 11 is needed）

#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <cstring>
#include <cassert>
#include <cctype>
#include <climits>
#include <ctime>
#include <iostream>
#include <algorithm>
#include <vector>
#include <string>
#include <stack>
#include <queue>
#include <deque>
#include <map>
#include <set>
#include <bitset>
#include <list>
#include <functional>
#define loop register int
typedef long long LL;
typedef unsigned long long ULL;
using std::cin;
using std::cout;
using std::endl;
typedef int INT_PUT;
INT_PUT readIn()
{
INT_PUT a = 0; bool positive = true;
char ch = getchar();
while (!(ch == '-' || std::isdigit(ch))) ch = getchar();
if (ch == '-') { positive = false; ch = getchar(); }
while (std::isdigit(ch)) { a = a * 10 - (ch - '0'); ch = getchar(); }
return positive ? -a : a;
}
void printOut(INT_PUT x)
{
char buffer[20]; int length = 0;
if (x < 0) putchar('-'); else x = -x;
do buffer[length++] = -(x % 10) + '0'; while (x /= 10);
do putchar(buffer[--length]); while (length);
}
int INF;
const int maxn = 505;
int n, w, h;
int rect[maxn][maxn];
typedef std::pair<int, int> Point;
Point pos[10];
enum { RIGHT, UP, LEFT, DOWN };
const int vecx[] = { 0, -1, 0, 1 };
const int vecy[] = { 1, 0, -1, 0 };
Point to[maxn][maxn][4];
int vis[maxn][maxn][4];
int stamp;
void DFS(int x, int y, int dir)
{
if (to[x][y][dir].first)
return;
vis[x][y][dir] = stamp;
int newz = dir;
if (rect[x][y] == -2)
newz = (newz + 1) & 3;
else if (rect[x][y] == -3)
newz = (newz + 4 - 1) & 3;
int newx = x + vecx[newz];
int newy = y + vecy[newz];
if (!(1 <= newx && newx <= h && 1 <= newy && newy <= w) || rect[newx][newy] == -1)
{
to[x][y][dir] = std::make_pair(x, y);
return;
}
else if (vis[newx][newy][newz] == stamp)
{
to[x][y][dir] = std::make_pair(-1, -1);
return;
}
DFS(newx, newy, newz);
to[x][y][dir] = to[newx][newy][newz];
}
void init()
{
for (loop x = 1; x <= h; x++)
for (loop y = 1; y <= w; y++)
for (loop i = 0; i < 4; i++)
{
stamp++;
DFS(x, y, i);
}
}
int f[10][10][maxn][maxn];
struct Queue
{
Point c[maxn * maxn];
int head, tail;
Queue() { clear(); }
void clear() { head = tail = 0; }
void push(const Point& x) { c[tail++] = x; }
void pop() { head++; }
Point front() { return c[head]; }
int val(int l, int r) { return f[l][r][c[head].first][c[head].second]; }
bool empty() { return head == tail; }
void sort(int l, int r)
{
std::sort(c + head, c + tail,
[=](const Point& a, const Point& b)
{
return f[l][r][a.first][a.second] < f[l][r][b.first][b.second];
});
}
} q1, q2;
bool inQ[maxn * maxn];
void SPFA(int l, int r)
{
q1.clear();
q2.clear();
for (loop x = 1; x <= h; x++)
for (loop y = 1; y <= w; y++)
if (f[l][r][x][y] < INF)
{
q1.push(std::make_pair(x, y));
inQ[x * w + y] = true;
}
q1.sort(l, r);
while (!(q1.empty() && q2.empty()))
{
Point from;
if (q2.empty() || (!q1.empty() && q1.val(l, r) <= q2.val(l, r)))
{
from = q1.front();
q1.pop();
}
else
{
from = q2.front();
q2.pop();
}
inQ[from.first * w + from.second] = false;
for (int i = 0; i < 4; i++)
{
const Point& t = to[from.first][from.second][i];
if (t.first == -1) continue;
int update = f[l][r][from.first][from.second] + 1;
int& ans = f[l][r][t.first][t.second];
if (update < ans)
{
ans = update;
if (!inQ[t.first * w + t.second])
{
q2.push(std::make_pair(t.first, t.second));
inQ[t.first * w + t.second] = true;
}
}
}
}
}
void solve()
{
memset(f, 0x3f, sizeof(f));
for (int i = 1; i <= n; i++)
f[i][i][pos[i].first][pos[i].second] = 0;
for (int len = 1; len <= n; len++)
{
for (int l = 1, r = l + len - 1; r <= n; l++, r++)
{
if (len > 1)
for (loop x = 1; x <= h; x++)
for (loop y = 1; y <= w; y++)
for (loop i = l; i < r; i++)
f[l][r][x][y] = std::min(f[l][r][x][y], f[l][i][x][y] + f[i + 1][r][x][y]);
SPFA(l, r);
}
}
int ans = INF;
for (int i = 1; i <= h; i++)
for (int j = 1; j <= w; j++)
ans = std::min(ans, f[1][n][i][j]);
if (ans >= INF)
printOut(-1);
else
printOut(ans);
}
void run()
{
memset(&INF, 0x3f, sizeof(INF));
n = readIn();
w = readIn();
h = readIn();
for (int x = 1; x <= h; x++)
{
for (int y = 1; y <= w; y++)
{
char ch = getchar();
while (!(std::isdigit(ch) || ch == '.' ||
ch == 'x' || ch == 'A' || ch == 'C'))
ch = getchar();
switch (ch)
{
case 'x': rect[x][y] = -1; break;
case 'A': rect[x][y] = -2; break;
case 'C': rect[x][y] = -3; break;
case '.': break;
default: pos[ch - '0'] = std::make_pair(x, y);
}
}
}
init();
solve();
}
int main()
{
run();
return 0;
}

关于 SPFA

  这道题我使用两个队列进行 SPFA 而不是一个，同时一开始还排了序，这是因为这样使得这个算法满足 BFS 的性质，即更新后的点不会再次被更新。这意味着时间复杂度为 O(n+m) O ( n + m ) 。

最后

以上就是鲜艳冰淇淋为你收集整理的Luogu 3638 [APIO 2013] 机器人的全部内容，希望文章能够帮你解决Luogu 3638 [APIO 2013] 机器人所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。