這道題做了好久，題并不難，一開始的思路，和做法都是對的。但是要求最小字典序必須從右向左求，這樣找最小的時(shí)候可以從左向右，保證最小字典序。以后做題特別要記住，越是情況多的時(shí)候越要總結(jié)歸納，最小樣例，最大樣例都要試一試，保證輸出正確。

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("\n%d\n",mind); 54 } 55 return 0; 56 }

?

轉(zhuǎn)載于:https://www.cnblogs.com/Acgsws/p/3198659.html

總結(jié)

以上是生活随笔為你收集整理的UVa116的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。