好贷网好贷款

UVa:116 Unidirectional TSP

发布时间:2016-12-3 17:40:58 编辑:www.fx114.net 分享查询网我要评论
本篇文章主要介绍了"UVa:116 Unidirectional TSP",主要涉及到UVa:116 Unidirectional TSP方面的内容,对于UVa:116 Unidirectional TSP感兴趣的同学可以参考一下。

  开始开了几个1000*1000的数组TLE到死,后来改小以后居然跑了个rank56.。。   确实是一道比较简单的动规。 状态转移方程是dp[i][j]=min{dp[i-1][j+1],dp[i][j+1],dp[i+1][j+1]}。   由于要输出字典序最小的情况所以当相等的时候要考虑一下三种情况的优先级。   不是很会写所以将一行和两行的情况单独处理了。   最后写了一百多行。。囧。。       #include <iostream> #include <cstdio> #include <cstring> #include <algorithm> using namespace std; int grid[11][101]; int path[11][101]; int dp[11][101]; int main() { int m,n; while(scanf("%d%d",&n,&m)!=EOF) { memset(grid,0,sizeof(grid)); memset(path,0,sizeof(path)); memset(dp,0,sizeof(dp)); for(int i=1; i<=n; ++i) for(int j=1; j<=m; ++j) scanf("%d",&grid[i][j]); int ans=0,key=0; if(n==1) { for(int j=1; j<=m; ++j) { ans+=grid[1][j]; path[1][j]=1; } printf("%d",1); for(int i=2; i<=m; ++i) printf(" %d",1); printf("\n%d\n",ans); } else if(n==2) { for(int i=m; i>=1; --i) for(int j=1; j<=n; ++j) { if(i==m) { dp[j][i]=grid[j][i]; path[j][i]=j; } else { if(dp[1][i+1]>dp[2][i+1]) { dp[j][i]=grid[j][i]+dp[2][i+1]; path[j][i]=2; } else { dp[j][i]=grid[j][i]+dp[1][i+1]; path[j][i]=1; } } } if(dp[1][1]>dp[2][1]) { ans=dp[2][1]; key=2; } else { ans=dp[1][1]; key=1; } printf("%d",key); int pos=path[key][1]; for(int i=2; i<=m; ++i) { printf(" %d",pos); pos=path[pos][i]; } printf("\n%d\n",ans); } else { for(int i=m; i>=1; --i) { for(int j=1; j<=n; ++j) { if(i==m) { dp[j][i]=grid[j][i]; path[j][i]=j; } else { if(j==1) { if(dp[j][i+1]<=dp[n][i+1]&&dp[j][i+1]<=dp[j+1][i+1]) { dp[j][i]=grid[j][i]+dp[j][i+1]; path[j][i]=j; } else if(dp[j+1][i+1]<=dp[j][i+1]&&dp[j+1][i+1]<=dp[n][i+1]) { dp[j][i]=grid[j][i]+dp[j+1][i+1]; path[j][i]=j+1; } else { dp[j][i]=grid[j][i]+dp[n][i+1]; path[j][i]=n; } } else if(j==n) { if(dp[1][i+1]<=dp[j-1][i+1]&&dp[1][i+1]<=dp[j][i+1]) { dp[j][i]=grid[j][i]+dp[1][i+1]; path[j][i]=1; } else if(dp[j-1][i+1]<=dp[j][i+1]&&dp[j-1][i+1]<=dp[1][i+1]) { dp[j][i]=grid[j][i]+dp[j-1][i+1]; path[j][i]=j-1; } else { dp[j][i]=grid[j][i]+dp[j][i+1]; path[j][i]=j; } } else { if(dp[j-1][i+1]<=dp[j][i+1]&&dp[j-1][i+1]<=dp[j+1][i+1]) { dp[j][i]=grid[j][i]+dp[j-1][i+1]; path[j][i]=j-1; } else if(dp[j][i+1]<=dp[j-1][i+1]&&dp[j][i+1]<=dp[j+1][i+1]) { dp[j][i]=grid[j][i]+dp[j][i+1]; path[j][i]=j; } else { dp[j][i]=grid[j][i]+dp[j+1][i+1]; path[j][i]=j+1; } } } } } int mn; for(int i=1; i<=n; ++i) { if(i==1||dp[i][1]<mn) { mn=dp[i][1]; key=i; } } ans=mn; printf("%d",key); int pos=path[key][1]; for(int i=2; i<=m; ++i) { printf(" %d",pos); pos=path[pos][i]; } printf("\n%d\n",ans); } } return 0; }  

上一篇:黑马程序员——Java基础---GUI
下一篇:LINUX移植——内核移植(一)

相关文章

相关评论