首页 > 代码库 > HDU5092

HDU5092

题意:找出从第1层到第n层的路径使得路径上的点和最小,若有多条选择最右的。

DP

#include<iostream>#include<cstdio>using namespace std;const long long NO=106;const long long INF=100000000000000000LL;long long n,m;long long MAP[NO][NO];long long pre[NO][NO];long long dp[NO][NO];void dfs(long long i,long long j){    if(i==1)    {        printf("%I64d",j);        return;    }    dfs(i-1,pre[i][j]);    printf(" %I64d",j);}int main(){    long long ttt,cas=1;    scanf("%I64d",&ttt);    while(ttt--)    {        printf("Case %I64d\n",cas++);        scanf("%I64d%I64d",&n,&m);        for(long long i=1;i<=n;i++)            for(long long j=1;j<=m;j++)                scanf("%I64d",&MAP[i][j]);        for(long long i=1;i<=n;i++)            dp[i][0]=dp[i][m+1]=INF;        for(long long i=0;i<=n;i++)            for(long long j=1;j<=m;j++)            {                dp[i][j]=dp[i-1][j+1];                pre[i][j]=j+1;                if(dp[i][j]>dp[i-1][j-1])                {                    dp[i][j]=dp[i-1][j-1];                    pre[i][j]=j-1;                }                if(dp[i][j]>dp[i-1][j])                {                    dp[i][j]=dp[i-1][j];                    pre[i][j]=j;                }                dp[i][j]+=MAP[i][j];            }        long long MIN=INF;        long long s=m;        for(long long j=m;j;j--)            if(MIN>dp[n][j])                MIN=dp[n][j],s=j;        dfs(n,s);        puts("");    }    return 0;}
View Code

 

HDU5092