hdu 5092 线裁剪(纵向连线最小和+输出路径)

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;

}