poj1040 Transportation（DFS）

题目链接

题意

城市A，B之间有m+1个火车站，第一站A站的编号为0，最后一站B站的编号为m，火车最多可以乘坐n人。火车票的票价为票上终点站的编号减去起点站的编号。输入火车票订单的数目orderNums，接着输入orderNums个订单，每个订单由3个数字s，e，p组成，分别表示订单的起点站，终点站，该订单的人数，必须全部接受订单上的乘客或者全部不接受，求铁路公司最多可以赚多少钱。

思路

对于一个订单来说，有两种情况：接受和不接受。我们只需将所有可能的情况枚举出来，然后求在每一种情况下，铁路公司所赚的钱的最大值即可，这种枚举很适合使用dfs来解决。为了简化求解，我们要保证乘客是按火车站的编号顺序来上车，所以要将订单按订单起点的编号从低到高排序，若起点相同，则按终点编号从低到高排序。

代码

 1 #include <algorithm>
 2 #include <iostream>
 3 #include <cstring>
 4 #include <cstdio>
 5 #include <vector>
 6 using namespace std;
 7 
 8 struct Order
 9 {
10     int s;  //起点
11     int e;  //终点
12     int p;  //人数
13 
14     Order(int s, int e, int p):s(s), e(e), p(p){}
15 };
16 
17 bool cmp(Order o1, Order o2)    //将订单排序
18 {
19     if(o1.s==o2.s)
20         return o1.e<o2.e;
21     return o1.s<o2.s;
22 }
23 
24 const int N = 10;
25 vector<Order> orders;
26 int n, m, orderNums;
27 int down[N];    //down[i]表示第i站下车的人数
28 int ans;
29 
30 /*
31 * p : 当前车上的人数
32 * cur : 当前处理第cur个订单
33 * sum : 当前赚的钱数
34 */
35 void dfs(int p, int cur, int sum)
36 {
37     if(cur==orderNums)
38     {
39         ans = max(ans, sum);
40         return;
41     }
42 
43     if(cur>0)   //减去上一个订单的下车人数
44     {
45         for(int i=orders[cur-1].s+1; i<=orders[cur].s; i++)
46             p-=down[i]; //减去下车的人数
47     }
48     if(p+orders[cur].p <= n)
49     {
50         down[orders[cur].e] += orders[cur].p;
51         dfs(p+orders[cur].p, cur+1, sum + (orders[cur].e-orders[cur].s)*orders[cur].p);
52         down[orders[cur].e] -= orders[cur].p;   //注意恢复现场，便于回溯
53     }
54     dfs(p, cur+1, sum);
55 }
56 
57 int main()
58 {
59     //freopen("poj1040.txt", "r", stdin);
60     while(cin>>n>>m>>orderNums && n)
61     {
62         ans = -1;
63         orders.clear();
64         memset(down, 0, sizeof(down));
65         for(int i=0; i<orderNums; i++)
66         {
67             int s, e, p;
68             cin>>s>>e>>p;
69             orders.push_back(Order(s, e, p));
70         }
71 
72         sort(orders.begin(), orders.end(), cmp);
73         dfs(0, 0, 0);
74         cout<<ans<<endl;
75     }
76     return 0;
77 }

一点思考

除了上面代码中的dfs写法，还可以换一种dfs写法，思路是在循环遍历订单时进行dfs，我感觉这种方法比上一种dfs方法要容易想一点，但实现起来比上一种要麻烦一些。代码和上面的代码基本一样，只是dfs函数有所不同。代码如下：

 1 #define _CRT_SECURE_NO_WARNINGS
 2 #include <algorithm>
 3 #include <iostream>
 4 #include <cstring>
 5 #include <cstdio>
 6 #include <vector>
 7 using namespace std;
 8 
 9 struct Order
10 {
11     int s;  //起点
12     int e;  //终点
13     int p;  //人数
14 
15     Order(int s, int e, int p) :s(s), e(e), p(p) {}
16 };
17 
18 bool cmp(Order o1, Order o2)    //将订单排序
19 {
20     if (o1.s == o2.s)
21         return o1.e<o2.e;
22     return o1.s<o2.s;
23 }
24 
25 const int N = 10;
26 vector<Order> orders;
27 int n, m, orderNums;
28 int down[N];    //down[i]表示第i站下车的人数
29 int ans;
30 
31 /*
32 * p : 当前车上的人数
33 * pre : 当前处理订单的上一个接受订单
34 * cur : 当前处理第cur个订单
35 * sum : 当前赚的钱数
36 */
37 void dfs(int p, int pre, int cur, int sum)
38 {
39     if (cur>0 && cur<orderNums)   //减去上一个订单的下车人数
40     {
41         for (int i = orders[pre].s + 1; i <= orders[cur].s; i++)
42             p -= down[i]; //减去下车的人数
43     }
44     for (int i = cur; i<orderNums; i++)
45     {
46         bool flag = false;
47         for (int j = orders[cur].s + 1; j <= orders[i].s; j++)    //测试是否能接受订单i
48         {
49             p -= down[j]; //减去下车的人数 (位置1)
50             flag = true;
51         }
52         if (p + orders[i].p <= n)
53         {
54             pre = i;
55             down[orders[i].e] += orders[i].p;
56             dfs(p + orders[i].p, pre, i + 1, sum + (orders[i].e - orders[i].s)*orders[i].p);
57             down[orders[i].e] -= orders[i].p;   //注意恢复现场，便于回溯
58         }
59         if (flag)    //只有在位置1减了的情况下再加回来
60         {
61             for (int j = orders[cur].s + 1; j <= orders[i].s; j++)
62                 p += down[j]; //加上位置1减去的人数,恢复现场，便于回溯
63         }
64     }
65     ans = max(ans, sum);
66 }
67 
68 int main()
69 {
70     //freopen("poj1040.txt", "r", stdin);
71     while (cin >> n >> m >> orderNums && n)
72     {
73         ans = -1;
74         orders.clear();
75         memset(down, 0, sizeof(down));
76         for (int i = 0; i<orderNums; i++)
77         {
78             int s, e, p;
79             cin >> s >> e >> p;
80             orders.push_back(Order(s, e, p));
81         }
82 
83         sort(orders.begin(), orders.end(), cmp);
84         dfs(0, 0, 0, 0);
85         cout << ans << endl;
86     }
87     return 0;
88 }

这份代码提交后内存占用与第一份代码相同，时间上稍微慢了一点点。