首页 > 代码库 > HDU 5092

HDU 5092

2024-07-30 18:41:47   215人阅读

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

卡读题，实质是每行取一个点，从上到下找一条路径权值和最小，点可以到达的地方是周围八个格子

类似数塔的dp，需要记录路径，当前行由上一行顶上的三个格子转移而来

#include <iostream>#include <cstdio>#include <queue>#include <cstring>#include <algorithm>#include <stack>using namespace std;int n,m;int a[105][105],dp[105][105],pre[105][105];int dx[]={-1,-1,-1};int dy[]={0,1,-1};struct node{    int x,y;};int main(){    int T;    scanf("%d",&T);    for(int cas=1;cas<=T;cas++){        scanf("%d%d",&n,&m);        for(int i=1;i<=n;i++){            for(int j=1;j<=m;j++){                scanf("%d",&a[i][j]);            }        }        for(int i=0;i<105;i++)            for(int j=0;j<105;j++)                dp[i][j]=0xfffffff;        for(int i=1;i<=m;i++)            dp[1][i]=a[1][i];        memset(pre,-1,sizeof(pre));        for(int i=2;i<=n;i++){            for(int j=1;j<=m;j++){                if(j-1>=1 && j+1<=m){                    //dp[i][j]=min(dp[i][j],a[i][j]+min(dp[i-1][j],min(dp[i-1][j-1],dp[i-1][j+1])));                    int t=min(dp[i-1][j],min(dp[i-1][j-1],dp[i-1][j+1]));                    if(a[i][j]+t<dp[i][j]){                        dp[i][j]=a[i][j]+t;                        if(dp[i-1][j+1]<=dp[i-1][j-1] && dp[i-1][j+1]<=dp[i-1][j])                            pre[i][j]=1;                        else if(dp[i-1][j]<=dp[i-1][j-1] && dp[i-1][j]<=dp[i-1][j+1])                            pre[i][j]=0;                        else pre[i][j]=2;                    }                }                else if(j-1>=1){                    //dp[i][j]=min(dp[i][j],a[i][j]+min(dp[i-1][j],dp[i-1][j-1]));                    int t=min(dp[i-1][j],dp[i-1][j-1]);                    if(a[i][j]+t<dp[i][j]){                        dp[i][j]=a[i][j]+t;                        if(dp[i-1][j]<=dp[i-1][j-1])                            pre[i][j]=0;                        else pre[i][j]=2;                    }                }                else if(j+1<=m){                    //dp[i][j]=min(dp[i][j],a[i][j]+min(dp[i-1][j],dp[i-1][j+1]));                    int t=min(dp[i-1][j],dp[i-1][j+1]);                    if(a[i][j]+t<dp[i][j]){                        dp[i][j]=a[i][j]+t;                        if(dp[i-1][j+1]<=dp[i-1][j])                            pre[i][j]=1;                        else pre[i][j]=0;                    }                }            }        }        int ans=0xfffffff;        int res;        for(int i=1;i<=m;i++){            //ans=min(ans,dp[n][i]);            if(ans>=dp[n][i]){                ans=dp[n][i];                res=i;            }        }        printf("Case %d\n",cas);        stack <node> s;        node st;        st.x=n;st.y=res;        s.push(st);        while(1){            if(st.x==1)break;            int xx=st.x+dx[pre[st.x][st.y]];            int yy=st.y+dy[pre[st.x][st.y]];            st.x=xx;st.y=yy;            s.push(st);        }        for(int i=1;i<=n;i++){            if(i==1)printf("%d",s.top().y);            else printf(" %d",s.top().y);            s.pop();        }        putchar(‘\n‘);    }    return 0;}
View Code

 

HDU 5092


联系
我们