dp

数据:d[i].a d[i].b d[i].v 分别表示第i条线段的起始点,结束点,价值

先按d[i].b排好序

dp[i]表示前i条线段的最大价值

方程:

dp[i]=max{ dp[i-1]

       d[i].v

       dp[p]+d[i].v  p<i,d[p].b<=d[i].a AND p最大

      }

这三种情况分别对应着:不放i,只放i,放前p个和i

因为dp是递增的,所以取满足d[p].b<=d[i].a(能放i)的最大的p即可

代码如下:

#include<iostream>
#include<algorithm>
#define Size 1005
using namespace std; int n;
int dp[Size];
struct L{
int a,b,v;
}d[Size]; bool cnt(L x,L y){
return x.b<y.b; //b小的在前面,b一样随便
} int main(){
cin>>n;
int x,y,v;
for(int i=;i<=n;i++){
cin>>x>>y>>v;
if(x>y)swap(x,y);
d[i].a=x;
d[i].b=y;
d[i].v=v;
} sort(d+,d++n,cnt); dp[]=;
for(int i=;i<=n;i++){
dp[i]=max(dp[i-],d[i].v);
for(int p=i-;p>;p--){
if(d[p].b<=d[i].a){
dp[i]=max(dp[i],dp[p]+d[i].v);
break;
}
}
//cout<<dp[i]<<endl;
} cout<<dp[n]<<endl; fclose(stdin);
return ;
}

最新文章

  1. WIN 下的超动态菜单(三)代码
  2. servlet/jsp详解
  3. JAVA 通过LDAP获取AD域用户及组织信息
  4. Unity Serialization
  5. [KOJ6997]旅行商问题二
  6. Jquery---用jQuery实现的智能隐藏、滑动效果的返回顶部代码
  7. 在Ubuntu系统中解压rar和zip文件的方法
  8. Day19 Django之Form表单验证、CSRF、Cookie、Session和Model操作
  9. NPOI扩展--判断指定单元格是否为合并单元格和输出该单元格的行列跨度(维度)
  10. EBS值集,弹性域常用表
  11. 20175214 《Java程序设计》第8周学习总结
  12. 15.1 打开文件时的提示(不是dos格式)去掉头文件
  13. emlog编辑器探寻之旅
  14. sudo配置教程
  15. 导出pdf
  16. linux下模拟FTP服务器(笔记)
  17. 4320: ShangHai2006 Homework
  18. [Eth]Mac/Phy/mdio/Rgmii
  19. PAT 1066 Root of AVL Tree
  20. freemarker ! 用法

热门文章

  1. Cousera 无法播放视频 解决办法 widows 和 linux
  2. python学习 (三十二) 异常处理
  3. iBatisNet分布式事务的应用 MS SQL2008。
  4. 翻译内核uvcvideo.txt
  5. input标签存在的兼容问题?
  6. 仅用CSS3创建h5预加载雷达圈
  7. C 语言 - Unicode 解决中文问题
  8. jquery easy ui 的formatter 格式化函数代码
  9. Python图片转字符
  10. 关于Android的margin(当前视图与周围视图的距离)和padding(当前视图与内部内容的距离)