UVA - 116 Unidirectional TSP 解题报告 (dp+路径还原)

时间：2022-12-12 20:34:39

题意：给出一个n*m的矩阵，让你找到一条从左到右的路径，使得路径上所有点之和最小。每一步可以选择右上、正右、右下三个点。

题目不难，我很快就找到了思路，但路径还原这部分我不太熟练，所以参考了紫书上的print_ans模板，稍作修改敲了上去，结果WA。然后我发现自己在对下标进行取模处理的时候忘了考虑它们大小的变化了，于是再稍事修改，结果还是WA。然后无论怎么改都AC不掉，前前后后WA了有7次。我怀疑自己用错了memcmp，于是把memcmp去掉，结果居然AC了。可是我用udebug测试的时候，是找不出错误的，我也不知道为啥。总之尽量不要用memcmp吧，QAQ。

AC代码：

#include<bits/stdc++.h>
#define FRER() freopen("i.txt","r",stdin)

using namespace std;
const int INF=0x3f3f3f3f;
int a[15][150],n,m,d[15][150],mini,ans[150],t[150];
int dp(int i,int j)
{
    if(j==m-1)
        return d[i][j]=a[i][j];
    if(d[i][j]!=INF)
        return d[i][j];
    for(int k=-1; k<=1; ++k)
        d[i][j]=min(d[i][j],a[i][j]+dp(((i+k)+n)%n,j+1));
    return d[i][j];
}
void print_ans(int i,int j)
{
    ans[j]=i;
    if(j==m-1)
        return;
    int index[3];
    for(int ii=0,k=-1; k<=1; ++k,++ii)
        index[ii]=((i+k)+n)%n;
    sort(index,index+3);
    for(int k=0; k<3; ++k)
        if(d[i][j]==a[i][j]+d[index[k]][j+1])
        {
            print_ans(index[k],j+1);
            break;
        }
}
void test()
{
    for(int i=0; i<m; ++i)
    {
        if(i>0)
            printf(" ");
        printf("%d",ans[i]+1);
    }
    printf("\n");
}
int main()
{
    //FRER();
    while(scanf("%d%d",&n,&m)==2)
    {
        for(int i=0; i<n; ++i)
            for(int j=0; j<m; ++j)
                scanf("%d",&a[i][j]);
        mini=INF;
        memset(ans,INF,sizeof ans);
        for(int i=0; i<n; ++i)
        {
            memset(d,INF,sizeof d);
            dp(i,0);
            if(d[i][0]<mini)
            {
                print_ans(i,0);
                mini=d[i][0];
            }
        }
        test();
        printf("%d\n",mini);
    }
    return 0;
}

然后我感觉这样做太麻烦，于是尝试了在更新dp值的同时记录下每个点的nxt值，相当于同时更新了dp值和nxt值

#include<bits/stdc++.h>
#define FRER() freopen("i.txt","r",stdin)

using namespace std;
const int INF=0x3f3f3f3f;
int a[15][150],n,m,d[15][150],mini,nxt[15][150],head;
int dp(int i,int j)
{
    if(j==m-1)
        return d[i][j]=a[i][j];
    if(d[i][j]!=INF)
        return d[i][j];
    for(int k=-1; k<=1; ++k)
    {
        int r=(i+k+n)%n;
        dp(r,j+1);
        if(d[r][j+1]+a[i][j]<d[i][j]||(d[r][j+1]+a[i][j]==d[i][j]&&r<nxt[i][j]))
            d[i][j]=d[r][j+1]+a[i][j],nxt[i][j]=r;
    }
    return d[i][j];
}
void test()
{
    for(int j=0, i=head; j<m; i=nxt[i][j],++j)
    {
        if(j>0)
            printf(" ");
        printf("%d",i+1);
    }
    printf("\n");
}
int main()
{
    //FRER();
    while(scanf("%d%d",&n,&m)==2)
    {
        for(int i=0; i<n; ++i)
            for(int j=0; j<m; ++j)
                scanf("%d",&a[i][j]);
        mini=INF;
        memset(d,INF,sizeof d);
        for(int i=0; i<n; ++i)
        {
            dp(i,0);
            if(d[i][0]<mini)
            {
                mini=d[i][0];
                head=i;
            }
        }
        test();
        printf("%d\n",mini);
    }
    return 0;
}

注意这里有个小技巧，就是用到了状态更新方程：

 if(d[r][j+1]+a[i][j]<d[i][j]||(d[r][j+1]+a[i][j]==d[i][j]&&r<nxt[i][j]))
            d[i][j]=d[r][j+1]+a[i][j],nxt[i][j]=r;

这是对两个带权值同时进行更新的通用操作。

然后我还不死心，索性去掉了递归，用自底而上的方式又重新写了一遍：

#include<bits/stdc++.h>
#define FRER() freopen("i.txt","r",stdin)

using namespace std;
const int INF=0x3f3f3f3f;
int a[15][150],d[15][150],mini,Index,n,m,nxt[15][150],head;
void test()
{
    for(int j=0, i=Index; j<m; i=nxt[i][j],++j)
    {
        if(j>0)
            printf(" ");
        printf("%d",i+1);
    }
    printf("\n");
}
int main()
{
    //FRER();
    while(scanf("%d%d",&n,&m)==2)
    {
        for(int i=0; i<n; ++i)
            for(int j=0; j<m; ++j)
                scanf("%d",&a[i][j]);
        memset(d,INF,sizeof d);
        for(int i=0; i<n; ++i)
            d[i][m-1]=a[i][m-1];
        for(int j=m-2; j>=0; --j)
            for(int i=0; i<n; ++i)
                for(int k=-1; k<=1; ++k)
                {
                    int r=(i+k+n)%n;
                    if(d[r][j+1]+a[i][j]<d[i][j]||(d[r][j+1]+a[i][j]==d[i][j]&&r<nxt[i][j]))
                        d[i][j]=d[r][j+1]+a[i][j],nxt[i][j]=r;
                }
        mini=INF;
        for(int i=0; i<n; ++i)
            if(d[i][0]<mini)
                mini=d[i][0],Index=i;
        test();
        printf("%d\n",mini);
    }
    return 0;
}

这样代码看起来简洁多了，而且速度也有了明显的提升。三次的耗时分别为120ms,80ms和50ms。

Misson Accomplished.

标签：

相关文章