【动态规划】mr351-办签证

【题目大意】

xuzhenyi要办个签证。办证处是一座M层的大楼，1<=M<=100。

每层楼都有N个办公室，编号为1..N(1<=N<=500)。每个办公室有一个签证员。

签证需要让第M层的某个签证员盖章才有效。

每个签证员都要满足下面三个条件之一才会给xuzhenyi盖章：

1. 这个签证员在1楼。

2. xuzhenyi的签证已经给这个签证员的正楼下（房间号相同）的签证员盖过章了。

3. xuzhenyi的签证已经给这个签证员的相邻房间（房间号相差1，楼层相同）的签证员盖过章了。

每个签证员盖章都要收取一定费用，这个费用不超过1000000000。

找出费用最小的盖章路线，使签证生效。

第1行两个整数M和N。

接下来M行每行N个整数，第i行第j个数表示第i层的第j个签证员收取的费用。

输出第1行为Min=最小费用。从第2行起按顺序输出你经过的房间的编号，每行一个数。

如果有多条费用最小的路线，输出任意一条。

样例输入 Sample Input

3 4

10 10 1 10

2 2 2 10

1 10 10 10

样例输出 Sample Output

Min=8

3

3

2

1

1

【思路】

简单动态规划，初始化第一层房间均为本房间签证价格，对于二层及以上的每一个房间，有三种可能性：

（1）从正楼下房间走上去，作为所有房间mincost数组的初始化。

（2）从左侧相邻房间走过来，从每层第二个房间开始，从左往右扫描。

（3）从右侧相邻房间走过来，从每层倒数第二个房间开始，从右往左扫描。

用path数组记录每间房间取到最小的价格时，是从哪一层的哪一个房间走过来的，然后倒序输出即可。

 #include<iostream>

 #include<cstdio>

 #include<cmath>

 using namespace std;

 const int MAXm=+;

 const int MAXn=+;

 struct node

 {

     int x,y;

 };

 int m,n;

 long long cost[MAXm][MAXn];

 long long mincost[MAXm][MAXn];

 node path[MAXm][MAXn];

 void init()

 {

     scanf("%d%d",&m,&n);

     for (int i=;i<m;i++)

        for (int j=;j<n;j++)

            scanf("%d",&cost[i][j]);

 }

 void dp()

 {

     for (int i=;i<n;i++)

     {

         mincost[][i]=cost[][i];

         path[][i].x=-;

         path[][i].y=-;

     }

     for (int i=;i<m;i++)

     {

         for (int j=;j<n;j++)

         {

             mincost[i][j]=mincost[i-][j]+cost[i][j];

             path[i][j].x=i-;

             path[i][j].y=j;

         }

         for (int j=;j<n;j++)

             if (mincost[i][j]>mincost[i][j-]+cost[i][j])

             {

                 mincost[i][j]=mincost[i][j-]+cost[i][j];

                 path[i][j].x=i;

                 path[i][j].y=j-;

             }

         for (int j=n-;j>=;j--)

             if (mincost[i][j]>mincost[i][j+]+cost[i][j])

             {

                 mincost[i][j]=mincost[i][j+]+cost[i][j];

                 path[i][j].x=i;

                 path[i][j].y=j+;

             }

     }

 }

 void print()

 {

     int ans=;

     for (int i=;i<n;i++) if (mincost[m-][i]<=mincost[m-][ans]) ans=i;

     cout<<"Min="<<mincost[m-][ans]<<endl;

     int nowx=m-,nowy=ans;

     int anspath[MAXm*MAXn],t=-;

     while (nowx!=-)

     {

         t++;

         anspath[t]=nowy;

         node next=path[nowx][nowy];

         nowx=next.x;

         nowy=next.y;

     }

     for (int i=t;i>=;i--) cout<<anspath[i]+<<endl;

 }

 int main()

 {

     freopen("mr351.in5","r",stdin);

     freopen("mr351.ou5","w",stdout);

     init();

     dp();

     print();

     return ;

 }

巴特西

【动态规划】mr351-办签证

最新文章

热门文章