做网站图片链接到天猫,苏州建设有限公司,上海网页制作公司,id注册网站题意翻译 Description 一个公司有三个移动服务员。如果某个地方有一个请求#xff0c;某个员工必须赶到那个地方去#xff08;那个地方没有其他员工#xff09;#xff0c;某一时刻只有一个员工能移动。只有被请求后#xff0c;他才能移动#xff0c;不允许在同样的位… 题意翻译 Description 一个公司有三个移动服务员。如果某个地方有一个请求某个员工必须赶到那个地方去那个地方没有其他员工某一时刻只有一个员工能移动。只有被请求后他才能移动不允许在同样的位置出现两个员工。从位置P到Q移动一个员工的费用是C(P, Q)。这个函数没有必要对称但是C(P, P) 0。一开始三个服务员分别在位置123公司必须满足所有的请求。 目标是最小化公司的费用。 Input 第1行2个整数LN(3L200, 1N1000). L是位置数每个位置从1到L编号N是请求数。 接下来L行每行包含L个非负整数第i1行的第j个数表示C(i, j)并且它小于2000. 最后一行包含N个数是请求列表。 Output 第1行一个数M表示最小的服务花费 输入输出样例 输入样例#1 1
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 输出样例#1 5 解析这题值得好好理解。是我滚动数组入门题目。 容易想到以当前的请求作为阶段当前服务员所在位置的最小花费作为状态。首先四维数组会爆空间。不用滚动数组也会爆空间。。。我们假设dp[i][x][y]表示在第i个请求时有一个服务员在x位置一个服务员在y位置。如果x和y都不在上一个请求所在位置那么剩下那个服务员必定在上一个请求的位置那里。我们有三种决策 将上一个请求位置的服务员转移到当前请求的位置上前提是x和y都不在上一个请求所在位置将x处的服务员转移到当前请求的位置上前提是y处的服务员不在当前请求的位置上注意上一个请求位置上的服务员不可能在此处了不需要此条件将y处的服务员转移到当前请求的位置上前提是x处的服务员不在当前请求的位置上我们很容易设计状态转移方程 if(x!p[i]y!p[i])dp[now][x][y]min(dp[now][x][y],dp[now^1][x][y]a[p[i-1]][p[i]]);
if(y!p[i])dp[now][p[i-1]][y]min(dp[now][p[i-1]][y],dp[now^1][x][y]a[x][p[i]]);
if(x!p[i])dp[now][x][p[i-1]]min(dp[now][x][p[i-1]],dp[now^1][x][y]a[y][p[i]]); 当然这些方程都有一个大前提就是当前请求的x和y既不能在同一个位置上又不能在上一个请求的位置上注意细节。 最后我们检查一遍最后一个请求时的状态找出最小值就OK了。 参考代码 1 #includeiostream2 #includecstdio3 #includecstring4 #includecmath5 #includealgorithm6 #includestring7 #includecstdlib8 #includequeue9 #includevector
10 #define INF 0x3f3f3f3f
11 #define PI acos(-1.0)
12 #define N 201
13 #define MOD 2520
14 #define E 1e-12
15 #define ri register int
16 using namespace std;
17 int a[N][N],dp[2][N][N],p[1001];
18 inline int read()
19 {
20 int f1,x0;char cgetchar();
21 while(c0||c9){if(c-)f-1;cgetchar();}
22 while(c0c9){xx*10c-0;cgetchar();}
23 return x*f;
24 }
25 int main()
26 {
27 int t;
28 cint;
29 while(t--)
30 {
31 memset(a,0,sizeof(a));
32 memset(p,0,sizeof(p));
33 int now0,l,n;
34 lread(),nread();
35 for(ri i1;il;i)
36 for(ri j1;jl;j) a[i][j]read();
37 for(ri i1;in;i) p[i]read();
38 memset(dp[now],0x3f,sizeof(dp));
39 p[0]3;dp[0][1][2]0;
40 for(ri i1;in;i){
41 now^1;//滚动数组
42 memset(dp[now],0x3f,sizeof(dp[now]));
43 for(ri x1;xl;x)//有l个地方可以去
44 if(x!p[i-1])
45 for(ri y1;yl;y)
46 {
47 if(xyyp[i-1]) continue;
48 if(x!p[i]y!p[i])
49 dp[now][x][y]min(dp[now][x][y],dp[now^1][x][y]a[p[i-1]][p[i]]);
50 if(y!p[i])
51 dp[now][p[i-1]][y]min(dp[now][p[i-1]][y],dp[now^1][x][y]a[x][p[i]]);
52 if(x!p[i])
53 dp[now][x][p[i-1]]min(dp[now][x][p[i-1]],dp[now^1][x][y]a[y][p[i]]);
54 }
55 }
56 int ansINF;
57 for(ri i1;il;i)
58 for(ri j1;jl;j)
59 if(i!ji!p[n]j!p[n])
60 ansmin(ans,dp[now][i][j]);//另一个人在p[n]处
61 coutansendl;
62 }
63 return 0;
64 } 转载于:https://www.cnblogs.com/DarkValkyrie/p/11053352.html
