http://acm.hdu.edu.cn/showproblem.php?pid=5092

給一個m*n的矩陣，找到一個縱向的"線"使得線上的和最小并輸出這條線，線能向8個方向延伸，要求找的是縱向的一條線(每一行各取一個點連成一線)

比較裸的dp，當前點只受到其上一行中的三個點的影響，然后求一下最大連和即可，dp過程中記錄路徑，然后打印時回溯即可

#include <cstdio> #include <cstdlib> #include <cmath> #include <cstring> #include <string> #include <queue> #include <map> #include <iostream> #include <algorithm> using namespace std; #define RD(x) scanf("%d",&x) #define RD2(x,y) scanf("%d%d",&x,&y) #define RD3(x,y,z) scanf("%d%d%d",&x,&y,&z) #define clr0(x) memset(x,0,sizeof(x)) #define clr1(x) memset(x,-1,sizeof(x)) #define eps 1e-9 const double pi = acos(-1.0); typedef long long LL; typedef unsigned long long ULL; const int modo = 1e9 + 7; const int INF = 0x3f3f3f3f; const int inf = 0x3fffffff; const LL _inf = 1e18; const int maxn = 105,maxm = 10005; int p[maxn][maxn],dp[maxn][maxn],col[maxn][maxn],n,m,cas = 1; char ch[maxn]; bool in(int x,int y) {return 1<=x&&x<=m&&1<=y&&y<=n; } void print(int x,int y) {if(x == 1){printf("%d",y);return ;}print(x - 1,col[x][y]);printf(" %d",y); } void work() {RD2(m,n);for(int i = 1;i <= m;++i)for(int j = 1;j <= n;++j){RD(p[i][j]);dp[i][j] = inf;}for(int j = 1;j <= n;++j)dp[1][j] = p[1][j];for(int i = 2;i <= m;++i)for(int j = n;j >= 1;--j){for(int k = j+1;k >= j-1;--k){if(in(i-1,k) && dp[i][j] > dp[i-1][k] + p[i][j]){dp[i][j] = dp[i-1][k] + p[i][j];col[i][j] = k;}}}int mn = inf;for(int j = n;j >= 1;--j)mn = min(mn,dp[m][j]);//printf("%d\n",mn);printf("Case %d\n",cas++);for(int j = n;j >= 1;--j)if(mn == dp[m][j]){print(m,j);puts("");return ;} } int main() {int _;RD(_);while(_--){work();}return 0; }

轉載于:https://www.cnblogs.com/zibaohun/p/4074368.html

總結

以上是生活随笔為你收集整理的hdu 5092 线裁剪(纵向连线最小和+输出路径)的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。