题目分析

本题描述了 TransRuratania 公司运营列车，列车有最大载客量$n$，车票价格根据起始站和终点站之间的车站数量确定，公司收集车票订单，需在订单接受策略下（对单个车站的订单完全接受或完全拒绝）计算最大总收益。

算法标签

DFS,回溯算法

解题思路

输入处理：

从输入文件中读取每一个数据块，提取列车载客容量$n$、城市B车站编号以及车票订单数量。对于每个订单，读取其起始站、终点站和乘客数量，并存储这些订单信息，方便后续处理。

枚举所有订单组合：

因为每个订单只有接受（状态为1）和拒绝（状态为0）两种状态，对于k个订单，总共有$2^k$种不同的订单组合情况。可以使用二进制数来表示每种组合，二进制数的每一位对应一个订单，通过遍历从0到$2^k - 1$的整数，将其转换为二进制形式，从而得到所有可能的订单组合。

检查可行性：

对于每一种订单组合，需要检查其是否满足列车载客容量的限制。遍历所有车站，计算在该订单组合下经过每个车站时列车上的乘客数量。如果在任何一个车站乘客数量超过列车载客容量$n$，则该组合不可行，跳过该组合。具体计算时，对于接受的订单，根据其起始站和终点站，在经过的车站上增加相应的乘客数量。

计算收益：

对于可行的订单组合，计算其总收益。每个订单的收益为乘客数量乘以起始站到终点站的站数（即车票价格）。将所有接受订单的收益相加，得到该订单组合的总收益。

找出最大收益：

在所有可行的订单组合中，找出总收益最大的组合，该组合的总收益即为公司可能获得的最大总收益。比较不同可行组合的总收益，记录最大值。

代码实现步骤（c++）

#include<cstdio>
#include<algorithm>
using namespace std;

#define BUFSIZE 25

struct orders{
 int from;
 int to;
 int person;
 int value;
}order[BUFSIZE];

int station[BUFSIZE];

int m,n,l,result,best;

int dfs(int ordernum,int remain)
{
 if(ordernum == l){
  if(result>best)best = result;
  return 0;
 }
 
 remain -= order[ordernum].value;
 
 for(int i = order[ordernum].from;i < order[ordernum].to;i++)
  station[i]+=order[ordernum].person;
 
 bool flag = false;
 for(int i= order[ordernum].from;i < order[ordernum].to;i++)
  if(station[i]>m)flag=true;
 
 if(!flag){
  result += order[ordernum].value;
  dfs(ordernum+1,remain);
  result -= order[ordernum].value;
 }
 
 for(int i = order[ordernum].from;i < order[ordernum].to;i++)
  station[i]-=order[ordernum].person;
 
 if(remain+result>best)
  dfs(ordernum+1,remain);
  
 return 0;
}
bool mycomp(struct orders a,struct orders b)
{
 return a.value>b.value;
}
int main()
{ 
 scanf("%d%d%d",&m,&n,&l);
 while(!(m==0&&n==0&&l==0)){
  
  int remain = 0;
  for(int i=0;i<l;i++){
   scanf("%d%d%d",&order[i].from,&order[i].to,&order[i].person);  
   order[i].value = (order[i].to - order[i].from)*order[i].person;
   remain += order[i].value;
  }
  fill_n(station,BUFSIZE,0);
  sort(order,order+l,mycomp);
  best = 0;
  result = 0;
  dfs(0,remain);
  printf("%d/n",best);
  scanf("%d%d%d",&m,&n,&l);
 }
 return 0;
}