（以“分类:序列动态规划 ==摘要== {{信息题|线段覆盖 2|http://www.codevs.cn/problem/3027/|1|100|time=2014/11/26 21:52:22|40|超时}} ==题意== 数轴...”为内容创建页面） |
小 （格式） |
||
| 第1行： | 第1行： | ||
[[分类:序列动态规划]] | [[分类:序列动态规划]] | ||
==摘要== | ==摘要== | ||
| − | {{信息题|线段覆盖 2|http://www.codevs.cn/problem/3027/|1|100|time=2014/11/26 21:52:22 | + | {{信息题|线段覆盖 2|http://www.codevs.cn/problem/3027/|1|100|time=2014/11/26 21:52:22|超时|40}} |
==题意== | ==题意== | ||
数轴上n条线段，各有价值，挑出若干，使两两不覆盖且价值之和最大。 | 数轴上n条线段，各有价值，挑出若干，使两两不覆盖且价值之和最大。 | ||
| 题目链接 | 难度等级 | 完成状态 | 完成分数 | 最后编辑时间 | 失误原因（初次提交分数） |
|---|---|---|---|---|---|
| 线段覆盖 2 | ★☆☆☆☆ | 答案正确 | 100 | 2014/11/26 21:52:22 | 超时（40） |
数轴上n条线段，各有价值，挑出若干，使两两不覆盖且价值之和最大。
首先先把点离散化掉（原数据排序，然后从大到小分别对应到1、2、3…），然后DP方程很容易想到：
CloudLunar
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;
}
|