CH 5102Mobile Service题解

用动态规划很容易将完成任务量作为dp的阶段，通过指派服务员，从当前i-1个任务转移到i个任务；

我们可以用一个四维数组f[i][x][y][z]来表示在完成当前任务i时，三个机器人分别在x，y，z的位置；每次由其中一个机器人向目标位置转移；取min值；

但是算法规模一点都不乐观；

我们想到在完成当前任务i时，必定存在一个机器人位于p[i],即目标地；那么我们可以用f[i][x][y],即完成任务i时，另外两个机器人位于x，y的位置；

状态转移：

f[k][i][j]=min(f[k][i][j],f[k-1][i][j]+c[p[k-1]][p[k]]);//k为当前完成任务，c数组记录两者间的距离，p数组为目标到达地；
f[k][p[k-1]][j]=min(f[k][p[k-1]][j],f[k-1][i][j]+c[i][p[k]]);
f[k][i][p[k-1]]=min(f[k][i][p[k-1]],f[k-1][i][j]+c[j][p[k]]);

不妨设p0=3，那么初始值f[0][1][2]=0;目标为f[N][?][?];

题后反思：

求解线性dp要注意阶段的选择，注意附加信息要处理；

确定状态时要注意选择最小的能表示整个状态的维度空间；

阶段保证无后效性；

#include<bits/stdc++.h>

#define maxl 201

#define maxn 1001

using namespace std;

int f[][][],n,m,t,l,c[][],p[],ans;

template<typename T>inline void read(T &x)

{

    x=;T f=,ch=getchar();

    while(!isdigit(ch)) ch=getchar();

    if(ch=='-') f=-, ch=getchar();

    while(isdigit(ch)) x=(x<<)+(x<<)+(ch^), ch=getchar();

    x*=f;

}

int main()

{

    read(t);

    while(t--) {

    int ans=;

    read(l);read(n);

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

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

            read(c[i][j]);

    memset(f,0x7f,sizeof(f));

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

        read(p[i]);

    }

    f[][][]=c[][p[]];

    f[][][]=c[][p[]];

    f[][][]=c[][p[]];

    p[]=,f[][][]=;

    for(int k=;k<=n;k++)

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

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

         if(i!=j&&p[k-]!=j&&p[k-]!=i)

         {

             f[k][i][j]=min(f[k][i][j],f[k-][i][j]+c[p[k-]][p[k]]);

             f[k][p[k-]][j]=min(f[k][p[k-]][j],f[k-][i][j]+c[i][p[k]]);

             f[k][i][p[k-]]=min(f[k][i][p[k-]],f[k-][i][j]+c[j][p[k]]);

         }

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

        for(int j=;j<=l;j++) {

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

                ans=min(ans,f[n][i][j]);

        }

    printf("%d\n",ans);

    }

    return ;

}

巴特西

CH 5102Mobile Service题解

最新文章

热门文章