Windarik is a happy man who seeks only happiness in his life. Even when he’s working, he consciously chooses tasks which make him happy. There are N agencies, and each agency offers zero or more tasks. A task is given in the form of an interval [A, B) which means this task should be done from exactly time unit A (inclusive) until right before time unit B (exclusive). Two tasks [A1, B1) and [A2, B2) where A1 ≤ A2 are conflicting if and only if B1 > A2 . It is guaranteed that there are no two conflicting tasks are from the same agency; subsequently, there are no guarantees for tasks between different agencies. Windarik has evaluated all available tasks from all agencies and assigned a happiness score H for each task, in which he would get if he decided to do that task. As a happy-oriented man, he needs to determine what is the maximum total happiness can be obtained by doing a set of carefully chosen tasks. Note that, among all the chosen tasks, there should be no two tasks which are conflicting to each other. For example, let there be 3 agencies: • Agency #1 offers 2 tasks: [10, 20) with happiness of 1, and [20, 60) with happiness of 1, • Agency #2 offers 2 tasks: [30, 50) with happiness of 2, and [60, 100) with happiness of 1, • Agency #3 offers 1 task: [20, 40) with happiness of 3. In this case, the maximum total happiness which can be obtained by Windarik is 5. He can obtained this by doing the first task from agency #1: [10, 20) with happiness of 1, the task only from agency #3: [20, 40) with happiness of 3, and the second task from agency #2: [60, 100) with happiness of 1. Thus, the total is 1 + 3 + 1 = 5. Notice that none of the chosen tasks are conflicting to each other. Windarik happiness is your responsibility; help him with this problem. As an incentive, Windarik will give you a balloon if you managed to solve this problem in four hours.
Input The first line of input contains an integer T (T ≤ 100) denoting the number of cases. Each case begins with two integers N and M (1 ≤ N ≤ 2, 000; 1 ≤ M ≤ 20, 000) in a line denoting the number of agencies and the total number of tasks in all agencies. The next M lines, each contains four integers: X A B H (1 ≤ X ≤ N; 0 ≤ A < B ≤ 106 ; 1 ≤ H ≤ 106 ) which represent a task from agency X which starts at time unit A and finished right before time unit B with happiness of H. It is guaranteed that no two tasks from the same agency are conflicting to each other. Output For each case, output ‘Case #X: Y ’ (without quotes) in a line where X is the case number (starts from 1), and Y is the answer for this particular case. Explanation for the sample: First case: This is the example given in the problem statement. Second case: All tasks are from the same agency (agency #1) and none are conflicting to each other. Thus, we can do all the tasks and obtained a maximum possible total happiness: 1 + 2 + 3 + 4 + 5 = 15. Third case: The maximum total happiness can be obtained by doing • The first task from agency #3: [0, 10) with happiness of 3, • The second task from agency #1: [10, 20) with happiness of 6. The total happiness is 3 + 6 = 9. Fourth case: The maximum total happiness can be obtained by doing: • The only task from agency #1: [10000, 30000) with happiness of 100, • The only task from agency #3: [30000, 50000) with happiness of 200, • The only task from agency #4: [50000, 70000) with happiness of 300, • The only task from agency #5: [80000, 90000) with happiness of 400. The total happiness is 100 + 200 + 300 + 400 = 1000. Sample Input 4 3 5 1 10 20 1 1 20 60 1 2 30 50 2 2 60 100 1 3 20 40 3 1 5 1 0 10 1 1 10 20 2 1 20 30 3 1 30 40 4 1 40 50 5 3 6 1 0 10 1 1 10 20 6 2 0 10 2 2 10 20 5 3 0 10 3 3 10 20 4 5 5 1 10000 30000 100 2 20000 40000 250 3 30000 50000 200 4 50000 70000 300 5 80000 90000 400 Sample Output Case #1: 5 Case #2: 15 Case #3: 9 Case #4: 1000
题意：给定n,m，(1 ≤ N ≤ 2, 000; 1 ≤ M ≤ 20, 000),n代表旅行社数量，m代表m个时间段 接下来m行X A B H ，x代表所属的旅行社，A代表时间段的左端点，B代表右端点，H为使用该时间段所获得的快乐值。 要求选出若干时间段，使得它们互不相交干涉，且能获得的最大快乐值。
分析：类似背包问题，先按照A从小到大排序，然后按B从小到大排序，按照选与不选两种来找最大快乐值
#include<cstring> #include<cstdio> #include<algorithm> using namespace std; #define mem(a,n) memset(a,n,sizeof(a)) const int N=20005; typedef long long LL; LL dp[N][2]; int n,m; struct node { LL s,e; LL w; bool operator < (const node &m)const { if(s!=m.s) return s<m.s; return e<m.e; } } a[N]; LL dfs(LL cnt,LL flag)///flag=0，为不选；=1，选 { if(cnt==m) return 0;//全部选取了 LL& ret=dp[cnt][flag]; if(ret!=-1) return ret;///若已经访问过，就有最大值 ret=dfs(cnt+1,0);///不选 //printf(" %lld\n",ret); for(int i=cnt+1;i<m;i++) { if(a[i].s-a[cnt].e>=0) ///选后面不冲突的一个 return ret=max(dfs(i,1)+a[cnt].w,ret);///取较大的那个 } return ret=max(ret,a[cnt].w);//返回较大的那个 } int main() { int t; scanf("%d",&t); for(int cas=1; cas<=t; cas++) { mem(dp,-1); scanf("%d%d",&n,&m); for(int i=0; i<m; i++) { LL x; scanf("%lld%lld%lld%lld",&x,&a[i].s,&a[i].e,&a[i].w); } sort(a,a+m); //for(int i=0; i<n; i++) // printf("%lld %lld %lld \n",a[i].s,a[i].e,a[i].w); LL ans=dfs(0,0); printf("Case #%d: %lld\n",cas,ans); } return 0; }