題意：給定一個n*m的矩陣，從第一列任意位置向右，右下，右上走一格，可以循環(huán)，要求經(jīng)過的數(shù)字的和最小。

思路：記憶化搜索。每次有三個狀態(tài)，從這三個狀態(tài)中選擇出最優(yōu)的一個，然后狀態(tài)累加，保存路徑。

code：

#include <bits/stdc++.h> using namespace std;const int N=11; const int M=105; #define ft(i,s,t) for (int i=s;i<=t;i++) #define frt(i,t,s) for (int i=t;i>=s;i--) int g[N][M],s[N][M];int main() {int n,m,t,tt;while (~scanf("%d %d",&n,&m)){ft(i,0,n-1) ft(j,0,m-1) scanf("%d",&g[i][j]);frt(j,m-2,0) ft(i,0,n-1){int bt=(i+n-1)%n;if (g[i][j+1]<g[bt][j+1]||g[i][j+1]==g[bt][j+1]&&bt>i) bt=i; //右上和直走的最優(yōu)解int t=(i+1)%n;if (g[t][j+1]<g[bt][j+1]||g[t][j+1]==g[bt][j+1]&&bt>t) bt=t;//右下和全部g[i][j]+=g[bt][j+1];s[i][j]=bt; //狀態(tài)記憶和保存路徑}int p=n-1;frt(i,n-2,0) if (g[p][0]>=g[i][0]) p=i;int ans=g[p][0];ft(i,0,m-2){printf("%d ",p+1);p=s[p][i];}printf("%d\n%d\n",p+1,ans);} }

總結

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

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