当前位置: 代码迷 >> 综合 >> 1383 移动服务 (codevs)
  详细解决方案

1383 移动服务 (codevs)

热度:54   发布时间:2023-12-17 02:51:19.0

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;
}