[JOYOI] 1061 Mobile Service

50 阅读 0 评论 33 点赞

我是靠谱客的博主辛勤石头，最近开发中收集的这篇文章主要介绍[JOYOI] 1061 Mobile Service，觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

题目限制
时间限制    内存限制    评测方式    题目来源
1000ms  131072KiB   标准比较器   Local
题目描述
一个公司有三个移动服务员。如果某个地方有一个请求，某个员工必须赶到那个地方去（那个地方没有其他员工），某一时刻只有一个员工能移动。被请求后，他才能移动，不允许在同样的位置出现两个员工。从p到q移动一个员工，需要花费c(p,q)。这个函数没有必要对称，但是c(p,p)=0。公司必须满足所有的请求。目标是最小化公司花费。

输入格式
第一行有两个整数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。

输出格式
一个数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
5

最朴素的设计是 f[i][x][y][z] 处理第i个请求时，三个人分别在x,y,z处，然后比较x,y,z到新请求地点的费用即可。

然后发现空间不够。。那就考虑优化它。

第一个是滚动数组，i行只依赖i-1行，这个很好想。

第二个是砍掉一维，因为在处理第i个请求时，上一个请求（i-1个）一定已经处理好了，所以三个人一定有一个站在ask[i-1]处，三维里有一维是冗余信息，所以
f[i][x][y] 表示处理第i个请求的时候，两个人站在x,y处(另一个在ask[i-1]处) 时的最小花费

边界的处理，令ask[0]=3，f[0][1][2] 就是三个人站在1,2,3处的初态。

//Stay foolish,stay hungry,stay young,stay simple
#include<iostream>
#include<cstdio>
#include<cctype>
#include<cstring>
using namespace std;

const int INF=1<<30;

inline int read_d(){
    int ret=0;char c;
    while(c=getchar(),!isdigit(c));
    while(isdigit(c)) ret=ret*10+c-'0',c=getchar();
    return ret;
}

int n,m;
int ask[1002];
int cost[202][202];
int f[2][202][202];

int main(){
    memset(f,0x3f,sizeof(f));
    n=read_d();m=read_d();
    for(int i=1;i<=n;i++)
        for(int j=1;j<=n;j++)
            cost[i][j]=read_d();
    for(int i=1;i<=m;i++)
        ask[i]=read_d();
    ask[0]=3;f[0][1][2]=0;
    int l=0,p=1;
    for(int i=1;i<=m;i++){
        memset(f[p],0x3f,sizeof(f[p]));
        l^=1;p^=1;
        int u=ask[i-1],v=ask[i];
        for(int j=1;j<=n+1;j++){
            for(int k=1;k<=n;k++){
                f[l][j][k]=
                min(f[l][j][k],f[p][j][k]+cost[ask[i-1]][v]);
                f[l][u][k]=
                min(f[l][u][k],f[p][j][k]+cost[j][v]);
                f[l][j][u]=
                min(f[l][j][u],f[p][j][k]+cost[k][v]);
            }
        }

    }
    int ans=INF;
    for(int i=1;i<=n;i++)
        for(int j=1;j<=n;j++)
            ans=min(ans,f[m&1][i][j]);
    cout<<ans<<endl;
    return 0;
}