UVa:301 Transportation

줄곧 검색 문제를 잘 쓰지 못했는데, 이 문제는 처음에 매우 엉망으로 썼다. TLE.주로 인원수를 어떻게 처리해야 할지 모르겠다.내가 처음에 한 방법은 매 역에 귀속한 다음에 매 역에 다시 귀속해서 매번 표를 예약하고 매번 인원수는 구조체로 보존하는 것이다. 이런 상태는 하나의 구조체로 서 있을 때 인원수를 늘리고 다음 역에 내릴 때 인원수를 줄이는 것이다.시간을 초과하다.
나중에 인터넷의 방법을 배웠다. 수조로 인원수를 표시하고 하나의 수조만 사용한다. 수조의 모든 요소는 매 역의 인원수를 표시한다. 이렇게 하면 이 수조는 현재 상태의 인원수를 표시하는데 나처럼 많은 공간을 낭비하지 않는다.이렇게 되면 매번 표를 예매하면 되고, 매 역의 문제를 고려할 필요가 없다.2^22번, 가지를 자르지 않았고, 시간을 초과하지 않았다.
 

#include <iostream>
#include <cstdlib>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <queue>
#include <vector>
#include <map>
#include <stack>
#include <algorithm>
#define MAXN 100005
#define MOD 1000000007
#define INF 100000000
#define ll long long
//ios::sync_with_stdio(false)
using namespace std;
int n,m,q;
struct Order
{
    int st,ed,peo,cost;
    Order(int a=0,int b=0,int c=0,int d=0):st(a),ed(b),peo(c),cost(d) {}
    bool operator < (const Order p) const
    {
        if(st==p.st) return ed<p.ed;
        return st<p.st;
    }
};
vector<Order> vec;
int people[30],maxn;
bool Judge(int st,int ed,int peo)
{
    for(int i=st; i<ed; ++i)
        if(people[i]+peo>n) return false;
    return true;
}
void dfs(int cur,int sum)
{
    if(cur>=q||vec[cur].st>=m) maxn=max(maxn,sum);
    else
    {
        if(Judge(vec[cur].st,vec[cur].ed,vec[cur].peo))
        {
            for(int i=vec[cur].st; i<vec[cur].ed; ++i)
                people[i]+=vec[cur].peo;
            dfs(cur+1,sum+vec[cur].cost);
            for(int i=vec[cur].st; i<vec[cur].ed; ++i)
                people[i]-=vec[cur].peo;
        }
        dfs(cur+1,sum);
    }
}
int main()
{

    while(scanf("%d%d%d",&n,&m,&q))
    {
        if(!n&&!m&&!q) break;
        int x,y,z;
        vec.clear();
        for(int i=0; i<q; ++i)
        {
            scanf("%d%d%d",&x,&y,&z);
            vec.push_back(Order(x,y,z,(y-x)*z));
        }
        sort(vec.begin(),vec.end());
        memset(people,0,sizeof(people));
        maxn=0;
        dfs(0,0);
        printf("%d
",maxn);
    }
    return 0;
}