POJ 2353 Ministry

  题目链接:http://poj.org/problem?id=2353

  题目要求的是这么一条路径:这条路径上所有数字的和最小,路径的走向只能向上、向左和向右。

  动态规划题,到达某个房间的当前值与其下方、左方和右方三个房间有关,那么,可以推出转移方程为:

  dp[i][j] = min(dp[i][j], dp[i][k] + sum[j][k])  (sum[j][k]为当前楼层从房间k到j的花费)

  对于上述方程,因为对于同一层楼的每一房间都枚举了其他所有房间,所以其复杂度为O(m*n*n),算法超时。

  如果思考再深入一点点,就会发现,如果最优路径经过某层楼编号在区间[a, b]的房间,那么区间[a, b]之间房间的最优花费都来自同一个方向,拿原题的图来说:

  

  如红色标记为最优路径,那么,对于第二层来说,房间1的最小值从房间2传过来,房间2的最小值又是从房间3传过来的,传递的方向是一致的,得到下面这条转移方程:

  dp[i][j] = a[i][j] + min(dp[i-1][j], dp[i][j-1], dp[i][j+1])

  当程序到达某一层楼时,先记录下从楼下传来的值,然后只需要向左扫一遍,再向右扫一遍记录最小值就行了,总复杂度O(m*n)。这个做法有一个很美妙的名字,叫“双向DP”。

View Code
 1 #include <stdio.h>
 2 #include <string.h>
 3 #include <math.h>
 4 #include <iostream>
 5 #include <algorithm>
 6 #include <vector>
 7 #include <map>
 8 #include <queue>
 9 using namespace std;
10 typedef long long LL;
11 const int maxn = 100 + 5;
12 const int maxm = 500 + 5;
13 
14 int a[maxn][maxm];
15 int dp[maxn][maxm];
16 int id[maxn][maxm];
17 
18 int main()
19 {
20     int n, m;
21     while(scanf("%d%d", &m, &n) == 2)
22     {
23         memset(dp, 0, sizeof dp);
24         for(int i = 1; i <= m; i++)
25             for(int j = 1; j <= n; j++)
26                 scanf("%d", &a[i][j]);
27         for(int i = m; i >= 1; i--)
28         {
29             for(int j = 1; j <= n; j++)  // 楼层传递
30             {
31                 dp[i][j] = dp[i+1][j] + a[i][j];
32                 id[i][j] = j;
33             }
34             
35             for(int j = 2; j <= n; j++)   // 向右DP
36             {
37                 if(dp[i][j-1] + a[i][j] < dp[i][j])
38                 {
39                     id[i][j] = id[i][j-1];
40                     dp[i][j] = dp[i][j-1] + a[i][j];
41                 }
42             }
43             
44             for(int j = n-1; j >= 1; j--)  // 向左DP
45             {
46                 if(dp[i][j+1] + a[i][j] < dp[i][j])
47                 {
48                     id[i][j] = id[i][j+1];
49                     dp[i][j] = dp[i][j+1] + a[i][j];
50                 }
51             }
52         }
53         int ans = 0x3fffffff;
54         int c, r;
55         for(int i = 1; i <= n; i++)
56         {
57             if(dp[1][i] < ans)
58                 ans = dp[1][i], r = 1, c = i;
59         }
60         for(int i = 1; i <= m; i++)        // 打印路径
61         {
62             int tmp = id[i][c];
63             if(tmp >= c)
64             {
65                 for(int i = c; i <= tmp; i++)
66                     printf("%d\n", i);
67             }
68             else if(tmp < c)
69                 for(int i = c; i >= tmp; i--)
70                     printf("%d\n", i);
71 
72             c = id[i][c];
73         }
74     }
75     return 0;
76 }
原文地址:https://www.cnblogs.com/huangfeihome/p/3063321.html