BZOJ1820 [JSOI2010]Express Service 快递服务

2014.12.19 12:45 Fri| 3 visits oi_2015| 2015_刷题日常| Text

Solution

感谢V字弦割丶的题解

没错,这是一道不错的DP。用 f[i][j][k] 表示当前三辆车所处位置分别为i、j、k时的最小花费。然后根据这道题的性质可以压掉一维。这样时间复杂度为 $\mathcal O(M^2\times K)$ (M为地点数,K为收件请求数)。

另外,V字弦割丶的代码不知为何好慢。事实上,这道题一点也不卡常数。

Code

#include <bits/stdc++.h>
using namespace std;
#define M 205
#define inf 0x3f3f3f3f

int m,f[2][M][M],dist[M][M];

inline int read()
{
    int x=0,f=1;char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
    while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
    return x*f;
}

int main()
{
    cin>>m;
    for(int i=1;i<=m;i++)
        for(int j=1;j<=m;j++)
            dist[i][j]=read();
    int pre=0,now=0,pos=0;
    memset(f,0x3f,sizeof f);
    f[0][1][2]=dist[3][pre=read()]; f[0][2][3]=dist[1][pre]; f[0][1][3]=dist[2][pre];
    while(scanf("%d",&now)!=EOF)
    {
        pos^=1;
        memset(f[pos],0x3f,sizeof f[pos]);
        for(int i=1;i<=m;i++)
            for(int j=i;j<=m;j++)
                f[pos][i][j]=f[pos][j][i]=min(f[pos][i][j],f[pos^1][i][j]+dist[pre][now]),
                f[pos][pre][j]=f[pos][j][pre]=min(f[pos][pre][j],f[pos^1][i][j]+dist[i][now]),
                f[pos][i][pre]=f[pos][pre][i]=min(f[pos][i][pre],f[pos^1][i][j]+dist[j][now]);
        pre=now;
    }
    int ans=inf;
    for(int i=1;i<=m;i++)
        for(int j=i;j<=m;j++)
            if(f[pos][i][j]<ans)
                ans=f[pos][i][j];
    cout<<ans<<endl;
}