SP703 SERVICE - Mobile Service[DP]

题意翻译

Description 　　一个公司有三个移动服务员。如果某个地方有一个请求，某个员工必须赶到那个地方去（那个地方没有其他员工），某一时刻只有一个员工能移动。只有被请求后，他才能移动，不允许在同样的位置出现两个员工。从位置P到Q移动一个员工的费用是C(P, Q)。这个函数没有必要对称，但是C(P, P) = 0。一开始三个服务员分别在位置1，2，3，公司必须满足所有的请求。目标是最小化公司的费用。 Input 　　第1行：2个整数L，N(3<=L<=200, 1<=N<=1000). L是位置数，每个位置从1到L编号，N是请求数。　　接下来L行，每行包含L个非负整数，第i+1行的第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：


解析：
这题值得好好理解。是我滚动数组入门题目。

容易想到以当前的请求作为阶段，当前服务员所在位置的最小花费作为状态。
首先，
四维数组会爆空间。不用滚动数组也会爆空间。。。

我们假设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^][x][y]+a[p[i-]][p[i]]);

if(y!=p[i])

    dp[now][p[i-]][y]=min(dp[now][p[i-]][y],dp[now^][x][y]+a[x][p[i]]);

if(x!=p[i])

    dp[now][x][p[i-]]=min(dp[now][x][p[i-]],dp[now^][x][y]+a[y][p[i]]);

当然，这些方程都有一个大前提，就是当前请求的x和y既不能在同一个位置上，又不能在上一个请求的位置上（注意细节）。

最后，我们检查一遍最后一个请求时的状态，找出最小值就OK了。

参考代码：

 #include<iostream>

 #include<cstdio>

 #include<cstring>

 #include<cmath>

 #include<algorithm>

 #include<string>

 #include<cstdlib>

 #include<queue>

 #include<vector>

 #define INF 0x3f3f3f3f

 #define PI acos(-1.0)

 #define N 201

 #define MOD 2520

 #define E 1e-12

 #define ri register int

 using namespace std;

 int a[N][N],dp[][N][N],p[];

 inline int read()

 {

     int f=,x=;char c=getchar();

     while(c<''||c>''){if(c=='-')f=-;c=getchar();}

     while(c>=''&&c<=''){x=x*+c-'';c=getchar();}

     return x*f;

 }

 int main()

 {

     int t;

     cin>>t;

     while(t--)

     {

         memset(a,,sizeof(a));

         memset(p,,sizeof(p));

         int now=,l,n;

         l=read(),n=read();

         for(ri i=;i<=l;i++)

          for(ri j=;j<=l;j++) a[i][j]=read();

         for(ri i=;i<=n;i++) p[i]=read();

         memset(dp[now],0x3f,sizeof(dp));

         p[]=;dp[][][]=;

         for(ri i=;i<=n;i++){

             now^=;//滚动数组

             memset(dp[now],0x3f,sizeof(dp[now]));

             for(ri x=;x<=l;x++)//有l个地方可以去

                 if(x!=p[i-])

                     for(ri y=;y<=l;y++)

                     {

                         if(x==y&&y==p[i-]) continue;

                         if(x!=p[i]&&y!=p[i])

                             dp[now][x][y]=min(dp[now][x][y],dp[now^][x][y]+a[p[i-]][p[i]]);

                         if(y!=p[i])

                             dp[now][p[i-]][y]=min(dp[now][p[i-]][y],dp[now^][x][y]+a[x][p[i]]);

                         if(x!=p[i])

                             dp[now][x][p[i-]]=min(dp[now][x][p[i-]],dp[now^][x][y]+a[y][p[i]]);

                     }

         }

         int ans=INF;

         for(ri i=;i<=l;i++)

          for(ri j=;j<=l;j++)

           if(i!=j&&i!=p[n]&&j!=p[n])

             ans=min(ans,dp[now][i][j]);//另一个人在p[n]处

         cout<<ans<<endl;

     }

     return ;

 }

巴特西

SP703 SERVICE - Mobile Service[DP]

题意翻译

输入输出样例

参考代码：

最新文章

热门文章