Hdu 4824 Disk Schedule (双调欧几里得旅行商问题)

谁践踏了优雅 2022-08-27 10:55 25阅读 0赞

2014百度之星资格赛1002

Poj 2677 和 Hdu 2224 也都是这类问题。学习资料：

[POJ2677 DP tour 双调欧几里得旅行商问题 - \_sunshine - 博客园][POJ2677 DP tour _ - _sunshine -]

[【算法学习】双调欧几里得旅行商问题（动态规划） - 江南烟雨 - 博客频道 - CSDN.NET][- _ - _ - CSDN.NET]

分析：首先，由于跳转一次磁道的消耗比在磁道上旋转一周还要大，所以尽量避免跳转磁道。那么最少的跳转方式，就是从0跳转到需要访问的最顶上的磁道，再从那里跳回来。

于是一来一回就成为了双调欧几里得旅行商问题的模型。

这题代码估计是我写复杂了，400+ms过的，看到有人的代码可以100+ms……

#include <cstdio>
    #include <cstring>
    #include <cmath>
    #include <algorithm>
    using namespace std;
    #define max(a,b) ((a)>(b)?(a):(b))
    #define max3(a,b,c) (max(a,max(b,c)))
    #define min(a,b) ((a)<(b)?(a):(b))
    
    const int N=1005;
    
    struct Point
    {
        int road,area;
        void Get ()
        {
            scanf("%d%d",&road,&area);
        }
        int Dis (Point b)
        {
            int tmp=fabs(b.area-area);
            return 400*fabs(b.road-road)+min( tmp,360-tmp);
        }
    }data[N];
    
    int dis[N][N];
    int dp[N][N];
    
    int main ()
    {
        int T,i,j,n;
        scanf("%d",&T);
        while (T--)
        {
            scanf("%d",&n);
            data[0].area=0;
            data[0].road=0;
            memset(dis,0,sizeof(dis));
            memset(dp,0,sizeof(dp));
            for (i=1;i<=n;i++)
                data[i].Get();
            for (i=0;i<=n;i++)
                for (j=i+1;j<=n;j++)
                    dis[i][j]=dis[j][i]=data[i].Dis(data[j]);
            dp[0][0]=0;
            n++;
            for (i=1;i<n;i++)
                dp[i][0]=dis[i][0];
            for (i=1;i<n-1;i++)
            {
                dp[i+1][i]=1000000000;
                for (j=0;j<=i-1;j++)
                {
                    dp[i+1][j]=dp[i][j]+dis[i][i+1];
                    dp[i+1][i]=min(dp[i+1][i],dp[i][j]+dis[j][i+1]);
                }
            }
            printf("%d\n",dp[n-1][n-2]+dis[n-1][n-2]+10*(n-1));
        }
        return 0;
    }

[POJ2677 DP tour _ - _sunshine -]: http://www.cnblogs.com/-sunshine/archive/2012/07/23/2605251.html
[- _ - _ - CSDN.NET]: http://blog.csdn.net/xiajun07061225/article/details/8092247