题目链接
一开始想写背包，然后发现不太一样，因为人们在中间可以下车。然后写了搜索也就是
设
为当前第
站，车上的人数为
，总价钱为
。因为按车一站一站地向前开，需要排序处理每个订单。然后搜索是这样写的：
void dfs(int cur,int num,int sum){if(cur==m){ans=max(ans,sum);return;}for(int i=0;i<q;i++) if(a[i].e==cur && vis[i]){num-=a[i].num;}dfs(cur+1,num,sum);for(int i=0;i<q;i++){if(a[i].s==cur && num+a[i].num<=n){vis[i]=1;dfs(cur+1,num+a[i].num,sum+a[i].w);vis[i]=0;}}
}
看起来没有问题，但是如果按照车一站一站向前开，每次都有可能有多个订单同时上车，这样在某一站可能同时有 个上或不上的状态，没办法正常搜索
正确的想法是：仍然按照站的先后顺序排序，设 为到终点为 的站下车的人数。按照所有订单的数目一个个地考虑，首先需要将上个订单的起点到终点的上车人数从总人数减去（如果没有就算减0），接着就考虑选择每个订单，更新相应终点站的人数，然后回溯到不选的状态；当然还需要考虑所有订单都不选，那么车站加一
#include <set>
#include <map>
#include <stack>
#include <queue>
#include <math.h>
#include <cstdio>
#include <string>
#include <bitset>
#include <cstring>
#include <sstream>
#include <iostream>
#include <algorithm>
using namespace std;
#define fi first
#define se second
#define pb push_back
#define ins insert
#define Vector Point
#define lowbit(x) (x&(-x))
#define mkp(x,y) make_pair(x,y)
#define mem(a,x) memset(a,x,sizeof a);
typedef long long ll;
typedef long double ld;
typedef unsigned long long ull;
typedef pair<int,int> pii;
typedef pair<double,double> pdd;
const double eps=1e-8;
const double pi=acos(-1.0);
const int inf=0x3f3f3f3f;
const double dinf=1e300;
const ll INF=1e18;
const int Mod=1e9+7;
const int maxn=1e6+10;struct node{int s,e,num;int w;bool operator < (const node& p) const{if(s==p.s) return e<p.e;return s<p.s;}
}a[30];
int n,m,q,ans;
int d[30];void dfs(int cur,int num,int sum){if(cur==q){ans=max(ans,sum);return;}if(cur>0) for(int i=a[cur-1].s+1;i<=a[cur].s;i++)num-=d[i];if(num+a[cur].num<=n){d[a[cur].e]+=a[cur].num;dfs(cur+1,num+a[cur].num,sum+a[cur].w);d[a[cur].e]-=a[cur].num;}dfs(cur+1,num,sum);
}int main(){//freopen("in.txt","r",stdin);//freopen("out.txt","w",stdout);ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);while(cin>>n>>m>>q && n){for(int i=0;i<q;i++){cin>>a[i].s>>a[i].e>>a[i].num;a[i].w=a[i].num*(a[i].e-a[i].s);}sort(a,a+q);//for(int i=0;i<q;i++) cout<<a[i].s<<" "<<a[i].e<<"-->"<<a[i].w<<endl;ans=0;dfs(0,0,0);cout<<ans<<endl;}return 0;
}