查看CodeVS/3027的源代码 ←CodeVS/3027

[[分类:序列动态规划]]
==摘要==
{{信息题|线段覆盖 2|http://www.codevs.cn/problem/3027/|1|100|time=2014/11/26 21:52:22|40|超时}}
==题意==
数轴上n条线段，各有价值，挑出若干，使两两不覆盖且价值之和最大。
==题解==
首先先把点离散化掉（原数据排序，然后从大到小分别对应到1、2、3…），然后DP方程很容易想到：
<pre>
    f[st][st+len]=max{f[st][st+slen]+f[st+slen][st+len]};//f[i][j]表示从第i个离散化的点到第j个点的最大价值
</pre>
这是O(<m>n^3</m>)的算法，会TLE。然后进一步优化，和石子归并等区间题不同的是，我们可以发现非从头开始的f都是没有意义的（这是序列动态规划和区间动态规划的区别），所以把st固定为1，得到：
<pre>
    f[len]=max(f[len],f[slen]+a[slen][len]);//f[i]表示从头到第i个点的最大价值
</pre>
详见代码。
==代码==
{{折叠|3027.cpp代码已折叠
|<pre>
#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;
}
</pre>
|code3027}}