UVA 116 Unidirectional TSP (백서 dp)

http://acm.hust.edu.cn:8080/judge/problem/viewProblem.action?id=18206  
1
 /*

  2     ：

  3            ，           ，    。（       ，     n m     ，      ，   ）

  4         
         

  5 

  6 

  7 

  8                ，  9             10 */

 11 dp[i][j]    [i][j]       

 12        ：

 13 dp[i][j]=min(dp[i-1][j+1],dp[i][j+1],dp[i+1][j+1]);

 14 next[i][j]    

 15 #include<stdio.h>

 16 #define maxn 200

 17 #define inf 0xfffffff

 18 #include<string.h>

 19 int min(int x,int y)

 20 {

 21     if(x<y)return x;

 22     else return y;

 23 

 24 }

 25 int n,m,next[maxn][maxn];

 26 int dp[maxn][maxn],map[maxn][maxn];

 27 void init()

 28 {

 29     int i,j;

 30     memset(next,0,sizeof(next));

 31     for(i=0;i<=n;i++)

 32     {

 33 

 34         for(j=0;j<=m;j++)

 35           dp[i][j]=inf;

 36     }

 37    for(i=1;i<=n;i++)

 38    {

 39        dp[i][m]=map[i][m];

 40    }

 41 }

 42 int  dfs(int x,int y)

 43 {

 44     int sum,d1,d3;

 45 

 46     if(y>m)return inf;

 47     if(dp[x][y]!=inf)return dp[x][y];

 48 

 49     int k;

 50     int x1,x2,x3;

 51 

 52     if(x-1==0)d1=n;

 53     else d1=x-1;

 54     if(x+1>n)d3=1;

 55     else d3=x+1;

 56 

 57     x1=dfs(d1,y+1);

 58     x2=dfs(x,y+1);

 59     x3=dfs(d3,y+1);

 60 

 61     if(x1>=inf&&x2>=inf&&x3>=inf){dp[x][y]=inf;return inf;}

 62     else

 63     {

 64         if(x1<x2)

 65         {

 66             sum=x1;

 67             k=d1;

 68         }

 69         else

 70         {

 71             if(x1==x2)

 72             {

 73                k=min(d1,x);

 74                sum=x1;

 75             }

 76             else

 77             {

 78                 k=x;

 79                 sum=x2;

 80             }

 81 

 82         }

 83         if(sum>x3)

 84         {

 85             k=d3;

 86             sum=x3;

 87 

 88         }

 89         else

 90         {

 91             if(sum==x3)

 92             {

 93                 k=min(k,d3);

 94             }

 95         }

 96         next[x][y]=k;

 97 

 98     dp[x][y]=dp[k][y+1]+map[x][y];

 99     return dp[x][y];

100 

101     }

102 

103 

104 

105 }

106 int GET()

107 {

108     int k,i,sum=inf;

109     for(i=1;i<=n;i++)

110     {

111         if(dp[i][1]<sum)

112         {

113             k=i;

114             sum=dp[i][1];

115         }

116     }

117     for(i=1;i<=m;i++)

118     {

119         if(i==1)

120         printf("%d",k);

121         else printf(" %d",k);

122         k=next[k][i];

123     }

124     printf("
%d
",sum);

125     return 0;

126 }

127 int main()

128 {

129     int i,j;

130     while(scanf("%d%d",&n,&m)!=EOF)

131     {

132 

133         for(i=1;i<=n;i++)

134         {

135             for(j=1;j<=m;j++)

136                scanf("%d",&map[i][j]);

137         }

138         init();

139        int ans=inf;

140        for(i=1;i<=n;i++)

141           dfs(i,1);

142 

143           /*for(i=1;i<=n;i++)

144           {

145               for(j=1;j<=m;j++)

146            {

147                 printf("%d ",dp[i][j]);

148 

149            }

150            printf("
");

151           }*/

152 

153           GET();

154     }

155 

156 }