题目链接

题意

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

思路

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

代码

1 #include 
     
       2 #include 
      
        3 #include 
       
         4 #include 
        
          5 #include 
         
           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
          
            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
           
            >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<
            
             <
            
           
          
         
        
       
      
     

 一点思考

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

1 #define _CRT_SECURE_NO_WARNINGS 2 #include 
     
       3 #include 
      
        4 #include 
       
         5 #include 
        
          6 #include 
         
           7 using namespace std; 8  9 struct Order10 {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
          
            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
           
            > n >> m >> orderNums && n)72 {73 ans = -1;74 orders.clear();75 memset(down, 0, sizeof(down));76 for (int i = 0; i
            
             > 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 }
            
           
          
         
        
       
      
     

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