第一次我理解错了题目，以为是最长路径问题，YY了N久，发现不对。我发现，它从1-3一定会经过2，而不是简单的最长路径问题，所以我们需要用回溯法来解决。

 

题目意思： 有一辆车从A城市开往B城市，途中有m个站，车上最多的载客人数为n人，每一个站的价格就是终点和起点的差值，现在有k分订单，要求找到这辆车的最大利润。

解题思路： 这一题如果我们去搜索站点，那么情况将会非常糟糕，但是如果我么去搜索订单，那么对于每一个订单而言就是取和不取，那么我们就可以知道这个解空间树的每一层就是一个订单，那么我们只要对这个订单编号，然后搜索订单即可。另外我们开一个数组，专门来存储每一个站点当前的人数，注意这里的人数处理，一份订单进来，那么起点---终点前一站都是要加上的，终点下车不用加，最后恢复现场。

 

CODE：

#include <iostream>

#include <cstdio>

#include <cstdlib>

#include <cstring>

#include <algorithm>

using 

namespace std;

#define MAXN 22

struct node

{

    

int u, v, cap;

}a[MAXN];

int A[MAXN];        

//

保存每个节点的最大存储量 

int ans;

int cap, stops, n;

void init()

{

    ans = 

0;

    memset(A, 

0, 

sizeof(A));

}

void dfs(

int cur, 

int n)

{

    

if(cur == n)

    {

        

int tot = 

0;

        

for(

int i = 

0; i < stops; i++) tot += A[i];

        

if(ans < tot) ans = tot;

    }

    

else

    {

        

bool ok = 

1;

        

for(

int i = a[cur].u; i < a[cur].v && ok; i++)

            

if(A[i] + a[cur].cap > cap) ok = 

0;

        

if(ok)

        {

            

for(

int i = a[cur].u; i < a[cur].v; i++) A[i] += a[cur].cap;

            dfs(cur+

1, n);     

//

接收订单 

            

for(

int i = a[cur].u; i < a[cur].v; i++) A[i] -= a[cur].cap;

        }

        dfs(cur+

1, n);         

//

不接收订单 

    }

}

int main()

{

    

while(~scanf(

"

%d%d%d

", &cap, &stops, &n) && (cap || stops || n)) 

//这而写 cap, stops, n就WA.

    {

        init();

        

for(

int i = 

0; i < n; i++)

            scanf(

"

%d%d%d

", &a[i].u, &a[i].v, &a[i].cap);

        dfs(

0, n);

        printf(

"

%d\n

", ans);

    }

    

return 

0;

}