【CH 5102】Mobile Service【DP】

本文主要是介绍【CH 5102】Mobile Service【DP】，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

题目大意：

题目链接：http://contest-hunter.org:83/contest/0x50「动态规划」例题/5102 Mobile Service
有三个服务员和$m$个地点，给定任意点到任意点的代价，求三个服务员在能到达所有地点的前提下总代价最小。

---

思路：

考虑深搜，把每种情况都求出来。（脑抽做法）

考虑费用流，所有点间依次建边，容量为1，代价为题目所给。（巨佬做法）
我不脑抽但也不是巨佬怎么办？
可以考虑蒟蒻做法DP。设$f[i][x][y][z]$为已经满足前$i$个请求，三个服务员分别在$x,y,z$的位置上的最小代价。但是时间复杂度$O(m{n}^3)$,不可取。
那么不甘心被卡的我们肯定会换一种算法一定会考虑优化DP。很容易发现，在第$i$个请求中，无论是$x,y,z$谁去完成这个请求，都肯定会到达请求的点，也就是说，第$i$个请求完成后，一定有一个人在请求的位置。那么我们就可以不用考虑没有人在请求位置的点的情况，成功降下一维。
设$f[x][y]$表示在完成第$i$个请求时，一个人在$x$，一个人在$y$，另外一个人在$w[i]$时的最小代价。那么有三个方程（因为三个人都可能去）：
$$f[k][i][j]=min(f[k][i][j],f[k-1][i][j]+w[ask[k-1]][ask[k]])$$
$$f[k][ask[k-1]][j]=min(f[k][ask[k-1]][j],f[k-1][i][j]+w[i][ask[k]])$$
$$f[k][i][ask[k-1]]=min(f[k][i][ask[k-1]],f[k-1][i][j]+w[j][ask[k]])$$

---

代码：

#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;int f[1001][201][201],n,m,w[201][201],ask[1001],ans;int main()
{memset(f,0x3f3f3f3f,sizeof(f));scanf("%d%d",&n,&m);for (int i=1;i<=n;i++)for (int j=1;j<=n;j++)scanf("%d",&w[i][j]);for (int i=1;i<=m;i++)scanf("%d",&ask[i]);f[0][1][2]=w[3][ask[1]];f[0][2][3]=w[1][ask[1]];f[0][1][3]=w[2][ask[1]];  //直接处理1的情况for (int k=1;k<=m;k++)for (int i=1;i<=n;i++)if (ask[k-1]!=i)for (int j=1;j<=n;j++)if (ask[k-1]!=j)if (i!=j){f[k][i][j]=min(f[k][i][j],f[k-1][i][j]+w[ask[k-1]][ask[k]]);f[k][ask[k-1]][j]=min(f[k][ask[k-1]][j],f[k-1][i][j]+w[i][ask[k]]);f[k][i][ask[k-1]]=min(f[k][i][ask[k-1]],f[k-1][i][j]+w[j][ask[k]]);}ans=2147483647;for (int i=1;i<=n;i++) for (int j=1;j<=n;j++)ans=min(ans,f[m][i][j]);printf("%d\n",ans);return 0;
}

这篇关于【CH 5102】Mobile Service【DP】的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---