UVa 301 - Transportation

301-Transportation

4584

32.83%

1338

76.08%

题目链接：

http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=108&page=show_problem&problem=237

题目类型： 回溯法

原题：

Ruratania is just entering capitalism and is establishing new enterprising activities in many fields including transport. The transportation company TransRuratania is starting a new express train from city A to city B with several stops in the stations on the way. The stations are successively numbered, city A station has number 0, city B station numberm. The company runs an experiment in order to improve passenger transportation capacity and thus to increase its earnings. The train has a maximum capacitynpassengers. The price of the train ticket is equal to the number of stops (stations) between the starting station and the destination station (including the destination station). Before the train starts its route from the city A, ticket orders are collected from all onroute stations. The ticket order from the station S means all reservations of tickets from S to a fixed destination station. In case the company cannot accept all orders because of the passenger capacity limitations, its rejection policy is that it either completely accept or completely reject single orders from single stations.

Write a program which for the given list of orders from single stations on the way from A to B determines the biggest possible total earning of the TransRuratania company. The earning from one accepted order is the product of the number of passengers included in the order and the price of their train tickets. The total earning is the sum of the earnings from all accepted orders.

Sample Input

10 3 4
0 2 1
1 3 5
1 2 7
2 3 10
10 5 4
3 5 10
2 4 9
0 2 5
2 5 8
0 0 0

Sample Output

19
34

题目大意：

有一家运输公司， 运营一段铁路， 该铁路A 站到B站。 从A站开始到B站编号为0....N-1。

每辆火车的限载人数为n人， 车票的价钱按站数计算，搭一个站收1元， n个站即n元。

为了让收益最大化， 每次开车前，都会先分析所有的车票，相同起点和终点的归为同一个订单。因为人数限制，如果人数太多的

话，就必须要放弃一些订单。 这个公司的做法有点极端， 要么整个订单都放弃，要么整个订单都接受。

编写一个程序，输出最大能收入多少钱。

分析与总结：

这题让我吐血TLE了无数次。

原因在于，按照惯性思维，和处理全排列的一样了， 开了个vis数组，然后递归遍历所有可能。而这一题和全排列不一样，

全排列是所有点最终都会访问到的，所以开vis数组标记很有必要，但是这题因为有些订单是不要的，对于不要的订单，以后都不会再去访问它， 而因为之前没有访问，所以vis数组上对它的记录还是停留在没有访问的状态，所以以后每次的递归都会再次去试探一下那些不要的订单，而试探的时候又要判断是否会超载，所以浪费的时间是十分巨大的！

所以，我就一直被催地TLE..............

解决这个问题， 可以不用开vis数组。 递归时，只往前面搜索，前面已经访问过的都不要回头再去访问一便，所以访问到的一定是没有访问过的。在递归函数中有一个参数cur， 表示的是当前要从数组中的那一个元素开始搜索， 然后这一次的递归就从那之后开始进行搜索。

如何表示车上的人数，检查是否超载？ 我是开了一个mark数组， 这个数组表示各个站上有多少人。每增加一个订单时，就把

这个订单的人数加到它的起始站到终点站（不包含终点站）上。 然后下次要检查是否超载时，就看这次加了人数之后，会不会有

超过限载人数的即可。

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#define MAXN 300
using namespace std;

int n, no_B, numTicket, maxSum, mark[MAXN], last[MAXN];
int status[MAXN];

struct Ticket{
    int start, end, num;
    int earn;
    int leftSum;
}arr[MAXN];


void dfs(int cur, int sum){
    if(sum > maxSum){
        maxSum = sum;
    }
    for( ; cur<numTicket; ++cur){
        int i;

        // 剪枝，如果剩下的都加上还比最大的小，直接退栈
        if(sum+arr[cur].leftSum < maxSum) return; 

        for(i=arr[cur].start; i<arr[cur].end; ++i){
            mark[i] += arr[cur].num;
            if(mark[i] > n) break; // 如果超过限载的话
        }
        if(i==arr[cur].end){ // 没有超过限载
            dfs(cur+1, sum+arr[cur].earn);
            --i;
        }
        for( ; i>=arr[cur].start; --i){
            mark[i] -= arr[cur].num;
        }
    }
}  


int main(){
#ifdef LOCAL
    freopen("input.txt","r",stdin);
#endif
    int order;
    while(scanf("%d %d %d", &n, &no_B, &order)!=EOF){
        if(!n && !no_B && !order) break;

        numTicket = 0;
        int a,b,c;

        for(int i=0; i<order; ++i){
            scanf("%d %d %d", &a, &b, &c);
            if(c <= n){ // 人数大于限制人数的订单不考虑
                arr[numTicket].start=a, arr[numTicket].end=b, arr[numTicket].num = c;
                arr[numTicket].earn = (b-a)*c;
                arr[numTicket++].leftSum = (b-a)*c;
            }
        }
        for(int i=numTicket-2; i>=0; --i)
            arr[i].leftSum += arr[i+1].leftSum;

        memset(vis, 0, sizeof(vis));
        memset(mark, 0, sizeof(mark));
        maxSum = -2147483646;
        dfs(0, 0);
        
        printf("%d\n", maxSum);
    }
    return 0;
}

—— 生命的意义，在于赋予它意义。

原创http://blog.csdn.net/shuangde800，By D_Double (转载请标明)