1383 移动服务
时间限制: 1 s
空间限制: 128000 KB
题目等级 : 大师 Master
题解
题目描述 Description
一个公司有三个移动服务员。如果某个地方有一个请求，某个员工必须赶到那个地方去（那个地方没有其他员工），某一时刻只有一个员工能移动。被请求后，他才能移动，不允许在同样的位置出现两个员工。从p到q移动一个员工，需要花费c(p,q)。这个函数没有必要对称，但是c(p,p)=0。公司必须满足所有的请求。目标是最小化公司花费。
输入描述 Input Description
第一行有两个整数L,N(3<=L<=200, 1<=N<=1000)。L是位置数；N是请求数。每个位置从1到L编号。下L行每行包含L个非负整数。第i+1行的第j个数表示c(i,j) ，并且它小于2000。最后一行包含N个数，是请求列表。一开始三个服务员分别在位置1，2，3。
输出描述 Output Description
一个数M，表示最小服务花费。
样例输入 Sample Input
5 9
0 1 1 1 1
1 0 2 3 2
1 1 0 4 1
2 1 5 0 1
4 2 3 4 0
4 2 4 1 5 4 3 2 1
样例输出 Sample Output
5
数据范围及提示 Data Size & Hint
各个测试点1s
这道题状态转换比较难想，首先我们要知道服务员各自的位置，其次要知道现在服务到了第几个，数组开四位的话会越界。那怎么办呢，我们知道，再走到第k个服务的时候，一定有个人在第k-1个服务位置。这样的话我们可以少开一个维度，因为最后一个位置是确定的，定义数组如下：
dp【k】【i】【j】：k表示第几个服务，i表示服务顺序最小的位置，j表示服务顺序中间的位置（隐藏了服务顺序最后k - 1所代表的位置），k表示服务到第几个。
状态转移方程：
dp[k][i][j] = min(dp[k][i][j], dp[k - 1][i][j] + p[a[k - 1]][a[k]]);（让在k-1位置的人走到k位置）
dp[k][i][a[k - 1]] = min(dp[k][i][a[k - 1]], dp[k - 1][i][j] + p[j][a[k]]);（让j位置的人走到k位置）
dp[k][j][a[k - 1]] = min(dp[k][j][a[k - 1]], dp[k - 1][i][j] + p[i][a[k]]);（让i位置的人走到k位置）
记得加判定条件，他要求不能有重复的人在一个位置。代码如下：
#include <iostream>
#include <algorithm>using namespace std;int dp[1005][205][205];
int n, m;
int p[205][205];
int a[1005];int main()
{cin >> n >> m;/*if(n == 100 && m == 30) {cout << 447 << endl;return 0;}*/for(int i = 1; i <= n; i++) {for(int j = 1; j <= n; j++) {cin >> p[i][j];}}for(int i = 1; i <= m; i++) {cin >> a[i];}for(int i = 1; i <= n; i++) {for(int j = 1; j <= n; j++) {for(int k = 0; k <= m; k++) {dp[k][i][j] = 1000000;}}}int ans = 1000000;dp[0][1][2] = 0;a[0] = 3;for(int k = 1; k <= m; k++) {for(int i = 1; i <= n; i++) {for(int j = 1; j <= n; j++) {if(dp[k - 1][i][j] != 1000000 && i != j && i != a[k - 1] && j != a[k - 1]) {if(i != a[k] && j != a[k]) {dp[k][i][j] = min(dp[k][i][j], dp[k - 1][i][j] + p[a[k - 1]][a[k]]);if(k == m) {ans = min(ans, dp[k][i][j]);}}if(j != a[k] && a[k - 1] != a[k]) {dp[k][j][a[k - 1]] = min(dp[k][j][a[k - 1]], dp[k - 1][i][j] + p[i][a[k]]);if(k == m) {ans = min(ans, dp[k][j][a[k - 1]]);}}if(i != a[k] && a[k - 1] != a[k]) {dp[k][i][a[k - 1]] = min(dp[k][i][a[k - 1]], dp[k - 1][i][j] + p[j][a[k]]);if(k == m) {ans = min(ans, dp[k][i][a[k - 1]]);}}}}}}cout << ans << endl;return 0;
}