POJ 2353 Ministry（DP，前缀）-白红宇

POJ 2353 Ministry（DP，前缀）

阅读量：6312 次

发布时间：2019-06-22

本文共 1542 字，大约阅读时间需要 5 分钟。

POJ 2353 Ministry

题意：

给你一个n*m的矩阵，每个矩阵有一个数，表示在位置（i，j）办理手续的费用，在（i，j）办理完手续之后，你可以到（i+1，j）或者（i，j+1）或者（i，j-1）的位置继续办理手续，办完所有的手续定义为从（1，j）开始,到（n，j’）结束的整个过程，要求你求出办完手续的最小费用，并且输出方案。

解题过程：

我们首先可以想到DP的方法，但是对于（i，j）有三种转移的来源，为了不漏掉方案，我们可以对于每一行进行从左往右和从右往左的两次DP，然后用pre数组记录前缀用于输出方案就行了。

AC代码：

#pragma GCC optimize (3)#include 
    
     #include 
     
      #include 
      
       #include 
       
        #include 
        
         #include 
         
          #include 
          #include 
           
            #include 
            
             #include 
             
              #include 
              
               using namespace std;typedef long long ll;const ll inf=1e15;const int maxn=505;ll f[maxn][maxn];int pre[maxn][maxn];int n,m;ll fee[maxn][maxn];int main() { scanf("%d%d",&n,&m); for(int i=0;i<=n+1;i++) { for(int j=0;j<=m+1;j++) { fee[i][j]=inf; } } for(int i=1;i<=n;i++) { for(int j=1;j<=m;j++) { scanf("%lld",&fee[i][j]); pre[i][j]=j; } } for(int i=0;i<=n;i++) { for(int j=0;j<=m;j++) { f[i][j]=inf; } } for(int i=1;i<=m;i++) f[1][i]=fee[1][i]; for(int i=2;i<=n;i++) { f[i][1]=f[i-1][1]+fee[i][1]; for(int j=2;j<=m;j++) { if(f[i-1][j]>f[i][j-1]) { pre[i][j]=j-1; } f[i][j]=min(f[i-1][j],f[i][j-1])+fee[i][j]; } ll temp=f[i][m]; f[i][m]=f[i-1][m]+fee[i][m]; for(int j=m-1;j>=1;j--) { if(f[i][j+1]+fee[i][j]
               
                temp) { pre[i][m]=m-1; } } ll minx=inf; int pos; for(int i=1;i<=m;i++) { if(f[n][i]

ans; ans.push_back(pos); while(ii>1) { ans.push_back(pre[ii][pos]); if(pos==pre[ii][pos]) { ii--; } else { pos=pre[ii][pos]; } } for(int i=ans.size()-1;i>=0;i--) { printf("%d\n",ans[i]); } return 0;}

本人蒟蒻OIer一枚，欢迎加QQ：840776708一起学习蛤。

转载于:https://www.cnblogs.com/Apocrypha/p/9433668.html

你可能感兴趣的文章

城市 | 800个地铁站数据透析的京沪白领图鉴：隐形土豪、无产中产阶级和猪猪女孩...