CodeVS/3027

摘要

题目链接	难度等级	完成状态	完成分数	最后编辑时间	失误原因（初次提交分数）
线段覆盖 2	★☆☆☆☆	答案正确	100	2014/11/26 21:52:22	超时（40）

题意

数轴上n条线段，各有价值，挑出若干，使两两不覆盖且价值之和最大。

题解

首先先把点离散化掉（原数据排序，然后从大到小分别对应到1、2、3…），然后DP方程很容易想到：

    f[st][st+len]=max{f[st][st+slen]+f[st+slen][st+len]};//f[i][j]表示从第i个离散化的点到第j个点的最大价值

这是O()的算法，会TLE。然后进一步优化，和石子归并等区间题不同的是，我们可以发现非从头开始的f都是没有意义的（这是序列动态规划和区间动态规划的区别），所以把st固定为1，得到：

    f[len]=max(f[len],f[slen]+a[slen][len]);//f[i]表示从头到第i个点的最大价值

详见代码。

代码

3027.cpp代码已折叠 展开折叠内容

#include<iostream> #include<cstdio> #include<algorithm> using namespace std; int pointsDced[1000001]={},f[3000],a[3000][3000],idTotal=0,n,points[3001]={-1},pointsSize=0,lhs[3001],rhs[3001],value[3001]; void discrete() { sort(points+1,points+pointsSize+1); for(int i=1;i<=pointsSize;++i) { if(points[i]==points[i-1]) continue; pointsDced[points[i]]=++idTotal; } } void init() { scanf("%d",&n); for(int i=1;i<=n;++i) { scanf("%d%d%d",&lhs[i],&rhs[i],&value[i]); points[++pointsSize]=lhs[i]; points[++pointsSize]=rhs[i]; } discrete(); for(int i=1;i<=n;++i) a[pointsDced[lhs[i]]][pointsDced[rhs[i]]]=value[i]; } void DP() { for(int len=1;len<=idTotal;++len)//错误修复：<=n -> <=idTotal for(int slen=1;slen<len;++slen) f[len]=max(f[len],f[slen]+a[slen][len]); } int main() { init(); DP(); cout<<f[idTotal]<<endl; }