UVA-116 - Unidirectional TSP

제목 링크 ~~>
문제풀이 깨달음: DAG를 하기 때문에 기억화로 쓰기 시작했는데 시간이 초과되어 동적 기획의 점차적인 형식으로 바꿀 수밖에 없었지만 번거롭게 썼다.
문제 해결 방법:
(1) 동적 계획을 점차적으로 미룬 후에 귀속적인 방법으로 사전 서열의 경로를 출력한다.
(2) 동적 기획 과정에서 줄 값을 끊임없이 기록하고 마지막으로 for 출력을 하면 된다.
코드(본인):

#include<stdio.h>
#include<queue>
#include<string.h>
#include<stdlib.h>
#include<string.h>
#include<algorithm>
#include<iostream>
#define INT long long int
const int INF = 99999999 ;
using namespace std ;
const int MX = 1000 + 10 ;
int n ,m,ans ;
bool first ;
int g[MX][MX],a[MX][MX] ;
void DP()
{
   for(int j=m-2 ;j>=0 ;j--)
    for(int i=0 ;i<n ;i++)
    {
        int mx=INF ;
        if(i==0)
        {
            if(g[i][j+1]<mx)
                 mx=g[i][j+1] ;
            if(g[i+1][j+1]<mx&&i+1<n)
                 mx=g[i+1][j+1] ;
            if(g[n-1][j+1]<mx)
                 mx=g[n-1][j+1] ;
        }
        else if(i==n-1)
        {
            if(g[0][j+1]<mx)
                mx=g[0][j+1] ;
            if(g[i-1][j+1]<mx&&i-1>=0)
                mx=g[i-1][j+1] ;
            if(g[i][j+1]<mx)
                mx=g[i][j+1] ;
        }
        else
        {
            if(g[i-1][j+1]<mx&&i-1>=0)
               mx=g[i-1][j+1] ;
            if(g[i][j+1]<mx)
               mx=g[i][j+1] ;
            if(g[i+1][j+1]<mx&&i+1<n)
               mx=g[i+1][j+1] ;
        }
        g[i][j]+=mx ;
    }
}
void print(int x,int y)
{
    if(first)   first=false,cout<<x+1 ;
    else        cout<<" "<<x+1 ;
    if(y==m-1)  return ;
    int  ans=g[x][y]-a[x][y] ;
    if(!x)
    {
        if(ans==g[x][y+1])
            print(x,y+1) ;
        else if(ans==g[x+1][y+1]&&x+1<n)
            print(x+1,y+1) ;
        else if(ans==g[n-1][y+1])
            print(n-1,y+1) ;
    }
    else if(x==n-1)
    {
        if(ans==g[0][y+1])
           print(0,y+1) ;
        else if(ans==g[x-1][y+1]&&x-1>=0)
           print(x-1,y+1) ;
        else if(ans==g[x][y+1])
           print(x,y+1) ;
    }
    else
    {
        if(ans==g[x-1][y+1]&&x-1>=0)
           print(x-1,y+1) ;
        else if(ans==g[x][y+1])
           print(x,y+1) ;
        else if(ans==g[x+1][y+1]&&x+1<n)
          print(x+1,y+1) ;
    }
}
int main()
{
    while(~scanf("%d%d",&n,&m))
    {
        first=true ;
        ans=INF ;
        for(int i=0 ;i<n ;i++)
         for(int j=0 ;j<m ;j++)
         {
             scanf("%d",&g[i][j]) ;
             a[i][j]=g[i][j] ;
         }
        DP() ;
        for(int i=0 ;i<n ;i++) //      
          if(ans>g[i][0])
             ans=g[i][0] ;
        for(int i=0 ;i<n ;i++)
          if(g[i][0]==ans)
          {
              print(i,0) ;
              break ;
          }
        printf("
") ;
        printf("%d
",ans) ;
    }
    return 0 ;
}

Premium 코드:

#include<stdio.h>
#include<queue>
#include<string.h>
#include<stdlib.h>
#include<string.h>
#include<algorithm>
#include<iostream>
#define INT long long int
const int INF = 99999999 ;
using namespace std ;
const int MX = 1000 + 10 ;
int n ,m ;
int g[MX][MX],d[MX][MX] ;
void DP()
{
   for(int i=m-2 ;i>=0 ;i--)
    for(int j=0 ;j<n ;j++)
    {
        int *p=&g[i+1][0] ;
        int Min=(j+1)%n,dn=(j-1+n)%n ;
        if(p[j]<p[Min]||(p[j]==p[Min]&&j<Min))
               Min=j ;
        if(p[dn]<p[Min]||(p[dn]==p[Min]&&dn<Min))
              Min=dn ;
        g[i][j]+=p[Min] ;
        d[i][j]=Min ; //        
    }
}
void print(int mx)
{
   cout<<mx+1 ;
   for(int i=1 ;i<m ;i++)
   {
       mx=d[i-1][mx] ;
       cout<<" "<<mx+1 ;
   }
}
int main()
{
    while(~scanf("%d%d",&n,&m))
    {
        for(int i=0 ;i<n ;i++)
         for(int j=0 ;j<m ;j++)
             scanf("%d",&g[j][i]) ;
        DP() ;
        int mx = min_element(&g[0][0],&g[0][n])-&g[0][0] ; //            
        int ans=g[0][mx] ;
        print(mx) ; //   
        cout<<endl<<ans<<endl ;
    }
    return 0 ;
}

이 내용에 흥미가 있습니까?

현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:

다양한 언어의 JSON

JSON은 Javascript 표기법을 사용하여 데이터 구조를 레이아웃하는 데이터 형식입니다. 그러나 Javascript가 코드에서 이러한 구조를 나타낼 수 있는 유일한 언어는 아닙니다. 저는 일반적으로 '객체'{}...

텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.

CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.

UVA-116 - Unidirectional TSP

좋은 웹페이지 즐겨찾기