题目描述
一个公司有三个移动服务员，最初分别在位置1，2，3处。
如果某个位置（用一个整数表示）有一个请求，那么公司必须指派某名员工赶到那个地方去。
某一时刻只有一个员工能移动，且不允许在同样的位置出现两个员工。
从 p 到 q 移动一个员工，需要花费 c(p,q)。
这个函数不一定对称，但保证 c(p,p)=0。
给出N个请求，请求发生的位置分别为 p1~pN。
公司必须按顺序依次满足所有请求，目标是最小化公司花费，请你帮忙计算这个最小花费。
输入格式
第1行有两个整数L,N，其中L是位置数量，N是请求数量，每个位置从1到L编号。
第2至L+1行每行包含L个非负整数，第i+1行的第j个数表示c(i,j) ，并且它小于2000。
最后一行包含N个整数，是请求列表。
一开始三个服务员分别在位置1，2，3。
输出格式
输出一个整数M，表示最小花费。
数据范围
3≤L≤200,
1≤N≤1000
输入样例：
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
输出样例：
5
---
思路如下：
DP的状态为已经完成的请求数量，通过指派一位服务员
可以把"完成i - 1个请求的状态"转移到"完成i个请求的状态"
那么我们可以知道转移从dp[i - 1] -> dp[i]
dp[i][x][y][z] 代表为第i次选择的情况下，对应的1,2,3号服务员
所对应的位置
那么可以得知
dp[i][arr[i]][y][z] = min(dp[i][arr[i]][y][z], dp[i - 1][x][y][z] + cost[x][arr[i]])
dp[i][x][arr[i]][z] = min(dp[i][x][arr[i]][z], dp[i - 1][x][y][z] + cost[y][arr[i]])
dp[i][x][y][arr[i]] = min(dp[i][x][y][arr[i]], dp[i - 1][x][y][z] + cost[z][arr[i]])
因为肯定有一个位置，继承了上一个的位置
所以保存两个状态就可以了
三种状态转移 pi,x,y
dp[i][x][y] = min(dp[i][x][y], dp[i - 1][x][y] + cost[pi - 1][pi])
dp[i][pi][y] = min(dp[i][pi][y], dp[i - 1][x][y] + cost[x][pi])
dp[i][x][pi] = min(dp[i][x][pi], dp[i - 1][x][y] + cost[y][pi])
dp[0][1][2] = 0;
for(int i = 1; i <= n; i ++)
{
for(int x = 1; x <= l; x ++)
{
for(int y = 1; y <= l; y ++)
{
if(x == y || x == arr[i] || y == arr[i])continue;
dp[i][x][y] = min(dp[i][x][y], dp[i - 1][x][y] + cost[temp][arr[i]]);
dp[i][pi][y] = min(dp[i][pi][y], dp[i - 1][x][y] + cost[x][pi]);
dp[i][x][pi] = min(dp[i][x][pi], dp[i - 1][x][y] + cost[y][pi]);
}
}
}
代码如下：
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 205;
int cost[MAXN][MAXN];
int arr[MAXN * 5];
int dp[1005][MAXN][MAXN];
typedef long long ll;
int l, n;
int main(){
scanf("%d%d", &l, &n);
for(int i = 1; i <= l; i ++){
for(int j = 1; j <= l; j ++){
scanf("%d", &cost[i][j]);
}
}
for(int i = 1; i <= n; i ++){
scanf("%d", &arr[i]);
}
arr[0] = 3;
for(int i = 0; i <= n; i ++){
for(int j = 1; j <= l; j ++){
for(int z = 1; z <= l; z ++){
dp[i][j][z] = 0x3f3f3f3f;
}
}
}
dp[0][1][2] = 0;
for(int i = 0; i < n; i ++){
for(int x = 1; x <= l; x ++){
for(int y = 1; y <= l; y ++){
if(x == y || x == arr[i] || y == arr[i]) continue;
dp[i + 1][x][y] = min(dp[i + 1][x][y], dp[i][x][y] + cost[arr[i]][arr[i + 1]]);
dp[i + 1][arr[i]][y] = min(dp[i + 1][arr[i]][y], dp[i][x][y] + cost[x][arr[i + 1]]);
dp[i + 1][x][arr[i]] = min(dp[i + 1][x][arr[i]], dp[i][x][y] + cost[y][arr[i + 1]]);
}
}
}
int re = 0x7fffffff;
for(int x = 1; x <= l; x ++){
for(int y = 1; y <= l; y ++){
re = min(re, dp[n][x][y]);
}
}
printf("%d\n", re);
return 0;
}