链接:
https://www.acwing.com/problem/content/276/
题意:
一个公司有三个移动服务员，最初分别在位置1，2，3处。
如果某个位置（用一个整数表示）有一个请求，那么公司必须指派某名员工赶到那个地方去。
某一时刻只有一个员工能移动，且不允许在同样的位置出现两个员工。
从 p 到 q 移动一个员工，需要花费 c(p,q)。
这个函数不一定对称，但保证 c(p,p)=0。
给出N个请求，请求发生的位置分别为 p1~pN。
公司必须按顺序依次满足所有请求，目标是最小化公司花费，请你帮忙计算这个最小花费。
思路:
Dp[i,j,k] 表示处理第i个请求,三个人分别在j,k,p位置的最小花费.
第一个写转移写错了..是吧转移到目标点的人给拿出去,同时在上一个目标点的人加到转移方程,
开始没搞懂.
代码:
#include <bits/stdc++.h>
using namespace std;
const int INF = 1e9;
int C[210][210];
int Pos[1010];
int Dp[1010][210][210];
int n, l;
int main()
{
scanf("%d%d", &l, &n);
for (int i = 1; i <= l; i++)
{
for (int j = 1; j <= l; j++)
scanf("%d", &C[i][j]);
}
for (int i = 1; i <= n; i++)
scanf("%d", &Pos[i]);
for (int i = 0; i <= n; i++)
{
for (int j = 1; j <= l; j++)
for (int k = 1; k <= l; k++)
Dp[i][j][k] = INF;
}
int p = 3;
Dp[0][1][2] = 0;
for (int i = 1; i <= n; i++)
{
for (int x1 = 1; x1 <= l; x1++)
{
for (int x2 = 1; x2 <= l; x2++)
{
if (x1 == x2 || x2 == p || x1 == p)
continue;
Dp[i][p][x2] = min(Dp[i][p][x2], Dp[i - 1][x1][x2] + C[x1][Pos[i]]);
Dp[i][x1][p] = min(Dp[i][x1][p], Dp[i - 1][x1][x2] + C[x2][Pos[i]]);
Dp[i][x1][x2] = min(Dp[i][x1][x2], Dp[i - 1][x1][x2] + C[p][Pos[i]]);
}
}
p = Pos[i];
}
int res = INF;
for (int x1 = 1; x1 <= l; x1++)
{
for (int x2 = 1; x2 <= l; x2++)
{
if (x1 == x2 || x2 == p || x1 == p)
continue;
res = min(res, Dp[n][x1][x2]);
}
}
printf("%d\n", res);
return 0;
}
/*
5 2
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
*/