题目链接：http://acm.hust.edu.cn/vjudge/problem/18206
题意：m*n的格子，每个格子里都有一个数，现在可以从第一列中任意一个格子出发，终点是到达最后一列格子。每次可以向右/右上/右下方向移动。而且第一行和最后一行是连着的（在第一行如果选择走右上的话会到达最后一行）。找到路径数值加和最小的路径，如果有多条，按照每一列行的字典序取最小的。
思路：直接枚举起点行数记忆化搜索即可，但是考虑最小方案，对于一个点(i,j)，要按照它可以到达三个点的字典序顺序去搜索，就可以得到字典序最小的路径。
#include <cstdio> #include <cmath> #include <cstring> #include <string> #include <cstdlib> #include <iostream> #include <algorithm> #include <stack> #include <map> #include <set> #include <vector> #include <sstream> #include <queue> #include <utility> using namespace std; #define rep(i,j,k) for (int i=j;i<=k;i++) #define Rrep(i,j,k) for (int i=j;i>=k;i--) #define Clean(x,y) memset(x,y,sizeof(x)) #define LL long long #define ULL unsigned long long #define inf 0x7fffffff #define mod 100000007 const int maxn = 109; int dp[maxn][maxn]; int a[maxn][maxn]; int Next[maxn][maxn];//记录路径 int n,m; int dfs( int x, int y ) { if ( y == m ) return a[x][y]; if ( dp[x][y] != -1 ) return dp[x][y]; int ans = 999999999; int way[] = { x , x % n + 1 , (x + n - 2)%n + 1 }; sort(way,way+3);//行序号字典序小的优先 rep(k,0,2) if ( ans > dfs( way[k] , y + 1 ) ) { ans = dfs( way[k] , y + 1 ); Next[x][y] = way[k]; } return dp[x][y] = ans + a[x][y]; } void solve() { Clean(dp,-1); int ans = 2099999999; int temp; rep(i,1,n) if ( ans > dfs( i , 1 ) ) { ans = dfs(i,1); temp = i; } rep(i,1,m) printf("%d%c",temp,i==m?'\n':' ') , temp = Next[temp][i]; printf("%d\n",ans); } int main() { while( cin>>n>>m ) { rep(i,1,n) rep(j,1,m) scanf("%d",&a[i][j]); solve(); } return 0; }
