1031.txt

来自「集合了SOJ（四川大学ACM在线评测系统）众多经典题目的详细解题报告」· 文本 代码 · 共 5 行

Transportation
题意：
    从一火车的起点到终点需要根据获得利润多少确定在某几个中间站中作出取舍，使得可以获得最多利润.
解法：
    此题其实是一道比较明显的搜索题，因为在计算过程中，应当将所有的站台情况考虑到，所以采用了分枝限界的方法，对从起点到终点的路径进行深度搜索。其中一个关键问题是中间状态的保存，因为火车每到一站，车上的乘客数会由于一部分乘客的下车和另一部分乘客的上车而变化从而导致总利润的变化，所以采用了一个一维数组，对搜索过程中每到一个站点乘客数量的变化进行记录，从而能够保证得到正确的最优解！