题目描述
【问题描述】
在《Harry Potter and the Chamber of Secrets》中，Ron的魔杖因为坐他老爸的Flying Car撞到了打人柳，不幸被打断了，从此之后，他的魔杖的魔力就大大减少，甚至没办法执行他施的魔咒，这为Ron带来了不少的烦恼。这天上魔药课，Snape要他们每人配置一种魔药（不一定是一样的），Ron因为魔杖的问题，不能完成这个任务，他请Harry在魔药课上(自然是躲过了Snape的检查)帮他配置。现在Harry面前有两个坩埚，有许多种药材要放进坩埚里，但坩埚的能力有限，无法同时配置所有的药材。一个坩埚相同时间内只能加工一种药材，但是不一定每一种药材都要加进坩埚里。加工每种药材都有必须在一个起始时间和结束时间内完成（起始时间所在的那一刻和结束时间所在的那一刻也算在完成时间内），每种药材都有一个加工后的药效。现在要求的就是Harry可以得到最大的药效。
出自:宜昌一中
输入格式
【输入】
输入文件的第一行有2个整数，一节魔药课的t（1≤t<≤500）和药材数n（1≤n≤100）。
输入文件第2行到n+1行中每行有3个数字，分别为加工第i种药材的起始时间t1、结束时间t2、（1≤t1≤t2≤t）和药效w（1≤w≤100）。
输出格式
【输出】
输出文件medic.out只有一行，只输出一个正整数，即为最大药效。
题解：
第一次做双线程动态规划，所以也就花了我星期三一个晚自习的时间。
设f[i][j]为坩埚1在第 i 的时间与坩埚2在第 j 的时间内所得最大药效。
可得动态转移方程：
f[i][j]=max{f[i][j],f[a[k][1]-1][j]} //i>=a[k][2]
f[i][j]=max{f[i][j],f[i][a[k][1]-1]} //j>=a[k][2]
满足了第 k 个物品只取入一个坩埚或不取。
当然，仅仅是这样还是不能保证能求出最优解，因为在计算过程中，结构会被刷新，因此对于结束时间较晚的药材，若在结束时间较前的药材先被计算，则较前的药材就以为价值小而不会被记录，因此就应该在动态规划之前将数据按结束时间a[i][2](即结束时间)升序排序。或者晚结束的药材更新的时候需要早结束的都更新过了的状态，方程才得以转移。
View Code
1 #include<iostream>
2 using namespace std;
3
4 int f[501][501]={0},a[101][3],w[101],n,m;
5
6 void quick(int l,int r){
7 if(l>=r) return ;
8 int i=l,j=r,mid=a[(l+r)/2][2];
9 while(i<=j)
10 {
11 while(a[i][2]<mid) i++;
12 while(a[j][2]>mid) j--;
13 if(i<=j)
14 {
15 if(a[i][2]==a[j][2]&&a[i][1]>a[j][1])
16 {i++;j--;continue;}
17 swap(a[i][1],a[j][1]);swap(a[i][2],a[j][2]);swap(w[i],w[j]);i++;j--;}
18 }
19 quick(l,j);
20 quick(i,r);
21
22 }
23
24 int main()
25 {
26 int i,j,k,l,z;
27 cin>>m>>n;
28
29 for(i=1;i<=n;i++)
30 cin>>a[i][1]>>a[i][2]>>w[i];
31
32 quick(1,n);
33
34 for(i=1;i<=n;i++)
35 for(k=m;k>=0;k--)
36 for(j=m;j>=0;j--)
37 {
38 if(j>=a[i][2]) f[j][k]=max(f[j][k],f[a[i][1]-1][k]+w[i]);
39 if(k>=a[i][2]) f[j][k]=max(f[j][k],f[j][a[i][1]-1]+w[i]);
40 }
41
42 cout<<f[m][m]<<endl;
43
44 return 0;
45
46 }