P7685 [CEOI2005] Mobile Service 题解

· · 题解

题目传送门

自然想到设 dp[i][x][y][z] 表示第 i 次服务后三人所在的位置。

易证存在最优方案使得每次服务后三人所在位置互不相同。

考虑到有一个位置肯定为 a_i，那么将这一维舍去。

重新设方程就是 dp[i][x][y] 表示第 i 次服务后不在 a_i 位置的剩下两个人所处位置分别为 x,y

若由 dp[i-1][x][y] 转移到下一次服务。分三种情况讨论：

如果 a_{i-1} 转移到 a_i，那么

dp[i][x][y]=\min\left\{dp[i-1][x][y]+C[a_{i-1}][a_i]\right\}

如果 x 转移到 a_i，那么

dp[i][a_{i-1}][y]=\min\left\{dp[i-1][x][y]+C[x][a_i]\right\}

如果 y 转移到 a_i，那么

dp[i][x][a_{i-1}]=\min\left\{dp[i-1][x][y]+C[y][a_i]\right\}

第二、三种情况会交换服务员的编号。

那如何输出方案呢？

交换编号和当前的 x,y 都要记录，但是如果内存限制很小那就无能为力了。

如果每一次服务的 x,y 都能知道，那么交换编号就可以正序遍历求出。

再看上面三种情况，第一种 x,y 都没有改变。

第二种 a_{i-1} 改变为 x，第三种 a_{i-1} 改变为 y。

那么在第二种或第三种情况记录 x 或 y。

如果被记录，就把 a_{i-1} 替换成 x 或 y。

为什么可以直接替换，因为 x,y 相同不会使答案更优，

所以 dp[i][a_{i-1}][a_{i-1}] 的情况可以被忽略掉。

然后记录下每次 x,y 正序遍历出答案即可。

记录一个编号直接用 unsigned char 即可，内存为 42MB 左右。

#include <cstdio>
#include <cctype>
#include <cstring>
using namespace std;
const int N=1011,M=211; unsigned char pos[N][M][M];
int m,n,f[2][M][M],res[N],a[N],cost[M][M],X[N],Y[N];
int iut(){
    int ans=0; char c=getchar();
    while (!isdigit(c)) c=getchar();
    while (isdigit(c)) ans=ans*10+c-48,c=getchar();
    return ans;
}
int main(){
    m=iut(); n=iut();
    for (int i=1;i<=m;++i)
    for (int j=1;j<=m;++j) cost[i][j]=iut();
    memset(f[0],0x3f,sizeof(f[0]));
    f[0][1][2]=0,a[0]=3,X[0]=1,Y[0]=2;
    for (int i=1;i<=n;++i) a[i]=iut();
    for (int i=1;i<=n;++i){
        memset(f[i&1],0x3f,sizeof(f[i&1]));
        for (int j=1;j<=m;++j)
        for (int k=1;k<=m;++k) if (j!=k)
        if (f[(i&1)^1][j][k]<f[0][0][0]){
            if (j!=a[i]&&k!=a[i]){
                int t=f[(i&1)^1][j][k]+cost[a[i-1]][a[i]];
                if (f[i&1][j][k]>t) f[i&1][j][k]=t,pos[i][j][k]=0;
            }
            if (a[i-1]!=a[i]&&k!=a[i]){
                int t=f[(i&1)^1][j][k]+cost[j][a[i]];
                if (f[i&1][a[i-1]][k]>t)
                    f[i&1][a[i-1]][k]=t,pos[i][a[i-1]][k]=j;
            }
            if (a[i-1]!=a[i]&&j!=a[i]){
                int t=f[(i&1)^1][j][k]+cost[k][a[i]];
                if (f[i&1][j][a[i-1]]>t)
                    f[i&1][j][a[i-1]]=t,pos[i][j][a[i-1]]=k;
            }
        }
    }
    int ans=f[0][0][0],mij,mik,F=1,G=2;
    for (int j=1;j<=m;++j)
    for (int k=1;k<=m;++k)
    if (j!=k&&f[n&1][j][k]<ans)
        ans=f[n&1][j][k],mij=j,mik=k;
    printf("%d\n",ans);
    for (int i=n;i>=1;--i){
        int t=pos[i][mij][mik]; X[i]=mij,Y[i]=mik;
        if (t) (mik==a[i-1])?(mik=t):(mij=t);
    }
    for (int i=1;i<=n;++i){
        if (X[i]==a[i-1]) F=6-F-G;
            else if (Y[i]==a[i-1]) G=6-F-G;
        printf("%d ",6-F-G);
    }
    return 0;
}