本文主要是介绍「BSOJ1418」 Tom的烦恼 - Dp，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
题目大意
有n个工作，每个工作有一个起始时间，结束时间和加工费，每个工作只能在限定的时间内完成，每做完一个工作可以获得该工作的加工费，在每一个时间段内只能做一个工作，问最多可获得的加工费。
分析
明显的DP，我一开始以为是一个背包，其实不是的。可以将每一个工作按照结束时间从小到大排序，然后就成为了一个类似最长不下降子序列问题的问题，可以理解为最大不下降子序列：每个节点有两个属性，编号和权值，选出一个编号不下降且权值最大的子序列。
用表示以
工作结尾所获得的最多加工费，则
其中表示起始时间，
表示结束时间，
表示加工费。
代码
#include <cstdio>
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
struct node {int a,b,v;
}lj[300005];
int n;
long long ans,f[300005];
bool cmp(const node&x,const node&y) {if (x.b!=y.b) return x.b<y.b;return x.a<y.a;
}
int main() {scanf("%d",&n);for (int i=1;i<=n;i++)scanf("%d%d%d",&lj[i].a,&lj[i].b,&lj[i].v);sort(lj+1,lj+n+1,cmp);f[1]=lj[1].v;ans=f[1];for (int i=2;i<=n;i++) {f[i]=lj[i].v;for (int j=1;j<i;j++) {if (lj[i].a>=lj[j].b)f[i]=max(f[i],f[j]+lj[i].v);}ans=max(ans,f[i]);}printf("%lld",ans);return 0;
}
这篇关于「BSOJ1418」 Tom的烦恼 - Dp的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
