UVa116

这道题做了好久，题并不难，一开始的思路，和做法都是对的。但是要求最小字典序必须从右向左求，这样找最小的时候可以从左向右，保证最小字典序。以后做题特别要记住，越是情况多的时候越要总结归纳，最小样例，最大样例都要试一试，保证输出正确。

 1 #include<stdio.h>
 2 #include<string.h>
 3 int main()
 4 {
 5     int m,n,mind,i,j,t,a[20][200],d[20][200],s[20][200];
 6     while(scanf("%d%d",&m,&n)!=EOF)
 7     {
 8         memset(d,0,sizeof(d));
 9         for(i=1;i<=m;i++)
10         for(j=n-1;j>=0;j--)
11         scanf("%d",&a[i][j]);
12         for(i=1;i<=m;i++)
13         d[i][0]=a[i][0];
14         for(j=1;j<n;j++)
15         for(i=1;i<=m;i++)
16         {
17             d[i][j]=d[i][j-1];
18              s[i][j]=i;
19             int t1=i+1;
20             if (t1>m)
21             t1=1;
22             if (d[i][j]==d[t1][j-1]&&s[i][j]>t1)
23                     s[i][j]=t1;
24             if (d[i][j]>d[t1][j-1])
25             {
26                 d[i][j]=d[t1][j-1];
27                 s[i][j]=t1;
28             }
29             int t2=i-1;
30             if(t2<1)
31             t2=m;
32             if(d[i][j]==d[t2][j-1]&&s[i][j]>t2)
33             s[i][j]=t2;
34             if (d[i][j]>d[t2][j-1])
35             {
36                 d[i][j]=d[t2][j-1];
37                 s[i][j]=t2;
38             }
39             d[i][j]+=a[i][j];
40         }
41         mind=d[1][n-1];t=1;
42         for(j=2;j<=m;j++)
43         if(d[j][n-1]<mind)
44         {
45             t=j;
46             mind=d[j][n-1];
47         } printf("%d",t);
48         for(i=n-1;i>=1;i--)
49         {
50             printf(" %d",s[t][i]);
51             t=s[t][i];
52         }
53         printf("
%d
",mind);
54     }
55     return 0;
56 }