一遍dp 要注意转移时它行号注意判断 因为它行是一个环
然后就是UVa一如既往令人窒息的输入输出
主要按的刘汝佳的思路
1 #include<iostream> 2 #include<cstdio> 3 #include<queue> 4 #include<cstring> 5 #include<cmath> 6 #include<stack> 7 #include<algorithm> 8 using namespace std; 9 #define ll long long 10 #define rg register 11 const int N=100+5,M=20,inf=0x3f3f3f3f; 12 int n,m,a[M][N],f[M][N],nxt[M][N],ans,fir; 13 template <class t>void rd(t &x) 14 { 15 x=0;int w=0;char ch=0; 16 while(!isdigit(ch)) w|=ch=='-',ch=getchar(); 17 while(isdigit(ch)) x=(x<<1)+(x<<3)+(ch^48),ch=getchar(); 18 x=w?-x:x; 19 } 20 21 int main() 22 { 23 //freopen("in.txt","r",stdin); 24 //freopen("nocows.out","w",stdout); 25 while(scanf("%d%d",&m,&n)==2)//m行n列 26 { 27 memset(a,0,sizeof(a)); 28 memset(nxt,0,sizeof(nxt)); 29 ans=inf; 30 for(rg int i=1;i<=m;++i) 31 for(rg int j=1;j<=n;++j) rd(a[i][j]); 32 for(rg int j=n;j>0;--j)//列 33 for(rg int i=1;i<=m;++i)//行 34 { 35 if(j==n) f[i][j]=a[i][j]; 36 else{ 37 int row[3]={i,(i-1+m)%m,(i+1)%m}; 38 if(!row[2]) row[2]=m;if(!row[1]) row[1]=m; 39 sort(row,row+3); 40 f[i][j]=inf; 41 for(rg int k=0;k<3;++k) 42 { 43 int v=a[i][j]+f[row[k]][j+1]; 44 if(v<f[i][j]) f[i][j]=v,nxt[i][j]=row[k]; 45 } 46 } 47 if(j==1&&f[i][j]<ans) ans=f[i][j],fir=i; 48 } 49 printf("%d",fir); 50 for(rg int i=nxt[fir][1],j=1;j<n;i=nxt[i][++j]) 51 printf(" %d",i); 52 printf(" %d ",ans); 53 } 54 return 0; 55 }