?
给一个m*n的矩阵，找到一个纵向的线使得线上的和最小并输出这条线，线能向8个方向延伸，要求找的是纵向的一条线(每一行各取一个点连成一线)
比较裸的dp，当前点只受到其上一行中的三个点的影响，然后求一下最大连和即可，dp过程中记录路径，然后打印时回溯即可
#include #include #include #include #include #include #include #include #include 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 ,mn); printf(Case %d ,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; }