Codeforces Round #355 (Div. 2) D. Vanya and Treasure dp+分块

题目链接：

http://codeforces.com/contest/677/problem/D

题意：

让你求最短的从start->...->1->...->2->...->3->...->...->p的最短路径。

题解：

这题dp的阶段性还是很明显的，相同的值得方格为同一个阶段，然后求从阶段1->2->3...->p的阶段图最短路。

初始化所有a[x][y]==1的格子为起始点到(x,y)坐标的距离。

方程式为dp[x1][y1]=min(dp[x1][y1],dp[x2][y2]+abs(x2-x1)+abs(y2-y1))，其中a[x1][y1]=a[x2][y2]+1。

但是这要n*n*m*m的复杂度。

x阶段到x+1阶段的转移数为cnt[x]*cnt[x+1]，这个太大，并且多来几个就会爆了，但注意如果cnt[x]*cnt[x+1]大了，其他的如

cnt[x']*cnt[x'+1]就有可能会变小，因为sum(cnt[i])是固定的，

那么根据这个特性，我们可以考虑分块！，当cnt[x]*cnt[x+1]<=m*n的时候直接暴力，如果大了就用最短路（spfa就可以）

这样跑出来的时间复杂度为O(n*m*sqrt(n*m)*log(n*m))，那个log(n*m)是spfa跑出来的。

具体的均摊时间复杂度证明：http://codeforces.com/blog/entry/45181?#comment-297475

代码：

#include<iostream> #include<cstdio> #include<cstring> #include<utility> #include<vector> #include<algorithm> #include<queue> #define mp make_pair #define X first #define Y second using namespace std;const int maxn = 305;int dp[maxn][maxn],mat[maxn][maxn]; int cnt[maxn*maxn],inq[maxn][maxn],d[maxn][maxn]; vector<pair<int,int> > G[maxn*maxn]; int n, m, p;inline int get_dis(int x1, int y1, int x2, int y2) {return abs(x1 - x2) + abs(y1 - y2); }const int dx[] = { -1,1,0,0 }; const int dy[] = { 0,0,-1,1 };void init() {memset(dp, 0x7f, sizeof(dp));memset(cnt, 0, sizeof(cnt)); }int main() {while (scanf("%d%d%d", &n, &m, &p) == 3 && n) {init();int xt, yt;for (int i = 0; i < n; i++) {for (int j = 0; j < m; j++) {scanf("%d", &mat[i][j]);if (mat[i][j] == 1) dp[i][j] = get_dis(0,0,i,j);if (mat[i][j] == p) xt = i, yt = j;cnt[mat[i][j]]++;G[mat[i][j]].push_back(mp(i, j));}}for (int i = 2; i <= p; i++) {if (cnt[i - 1] * cnt[i] <= m*n) {for (int j = 0; j < G[i].size(); j++) {int x2 = G[i][j].X, y2 = G[i][j].Y;for (int k = 0; k < G[i - 1].size(); k++) {int x1 = G[i - 1][k].X, y1 = G[i - 1][k].Y;dp[x2][y2] = min(dp[x2][y2], dp[x1][y1] + get_dis(x1, y1, x2, y2));}}}else {memset(d, 0x7f, sizeof(d));memset(inq, 0, sizeof(inq));queue<pair<int, int> > Q;for (int j = 0; j < G[i - 1].size(); j++) {pair<int, int> u = G[i - 1][j];d[u.X][u.Y] = dp[u.X][u.Y], inq[u.X][u.Y] = 1;Q.push(mp(u.X, u.Y));}while (!Q.empty()) {pair<int, int> u = Q.front(); Q.pop();inq[u.X][u.Y] = 0;if (mat[u.X][u.Y] == i) dp[u.X][u.Y] = min(dp[u.X][u.Y], d[u.X][u.Y]);for (int j = 0; j < 4; j++) {int x = u.X + dx[j], y = u.Y + dy[j];if (x < 0 || x >= n || y < 0 || y >= m) continue;if (d[x][y] > d[u.X][u.Y] + 1) {d[x][y] = d[u.X][u.Y] + 1;if (!inq[x][y]) inq[x][y] = 1, Q.push(mp(x, y));}}}}}printf("%d\n", dp[xt][yt]);}return 0; }

 

转载于:https://www.cnblogs.com/fenice/p/5554956.html

总结

以上是生活随笔为你收集整理的Codeforces Round #355 (Div. 2) D. Vanya and Treasure dp+分块的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。