【动态规划】mr351

【动态规划】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数组记录每间房间取到最小的价格时，是从哪一层的哪一个房间走过来的，然后倒序输出即可。

 1 #include<iostream>
 2 #include<cstdio>
 3 #include<cmath>
 4 using namespace std;
 5 const int MAXm=100+20;
 6 const int MAXn=500+20;
 7 struct node
 8 {
 9     int x,y;
10 };
11 int m,n;
12 long long cost[MAXm][MAXn];
13 long long mincost[MAXm][MAXn]; 
14 node path[MAXm][MAXn];
15 
16 void init()
17 {
18     scanf("%d%d",&m,&n);
19     for (int i=0;i<m;i++)
20        for (int j=0;j<n;j++)
21            scanf("%d",&cost[i][j]);
22 }
23 
24 void dp()
25 {
26     for (int i=0;i<n;i++) 
27     {
28         mincost[0][i]=cost[0][i];
29         path[0][i].x=-1;
30         path[0][i].y=-1; 
31     } 
32     for (int i=1;i<m;i++)
33     {
34         for (int j=0;j<n;j++) 
35         {
36             mincost[i][j]=mincost[i-1][j]+cost[i][j];
37             path[i][j].x=i-1;
38             path[i][j].y=j;
39         }
40         for (int j=1;j<n;j++)
41             if (mincost[i][j]>mincost[i][j-1]+cost[i][j])
42             {
43                 mincost[i][j]=mincost[i][j-1]+cost[i][j];
44                 path[i][j].x=i;
45                 path[i][j].y=j-1;
46             }
47         for (int j=n-2;j>=0;j--)
48             if (mincost[i][j]>mincost[i][j+1]+cost[i][j])
49             {
50                 mincost[i][j]=mincost[i][j+1]+cost[i][j];
51                 path[i][j].x=i;
52                 path[i][j].y=j+1;
53             }
54     }
55 }
56 
57 void print()
58 {
59     int ans=0;
60     for (int i=1;i<n;i++) if (mincost[m-1][i]<=mincost[m-1][ans]) ans=i;
61     cout<<"Min="<<mincost[m-1][ans]<<endl;
62     int nowx=m-1,nowy=ans;
63     int anspath[MAXm*MAXn],t=-1;
64     while (nowx!=-1)
65     {
66         t++;
67         anspath[t]=nowy;
68         node next=path[nowx][nowy];
69         nowx=next.x;
70         nowy=next.y;
71     }
72     for (int i=t;i>=0;i--) cout<<anspath[i]+1<<endl;
73 }
74 
75 int main()
76 {
77     freopen("mr351.in5","r",stdin);
78     freopen("mr351.ou5","w",stdout);
79     init();
80     dp();
81     print();
82     return 0;
83 }

转载于:.html