注册 登录  
 加关注
   显示下一条  |  关闭
温馨提示!由于新浪微博认证机制调整,您的新浪微博帐号绑定已过期,请重新绑定!立即重新绑定新浪微博》  |  关闭

东月之神

在单纯的观念里面,生命就容易变得比较深刻!

 
 
 

日志

 
 
关于我

别驻足,梦想要不停追逐,别认输,熬过黑暗才有日出,要记住,成功就在下一步,路很苦,汗水是最美的书!

网易考拉推荐

xmu 1162.寻找六星龙珠  

2010-04-28 15:52:42|  分类: ACM |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |
Description

    经过前面激烈的打斗,悟空的龙珠雷达坏掉了。为了继续寻找第六颗龙珠,现在只能找天才的发明家布玛来帮忙修好雷达了。等悟空来到布玛家时,布玛正忙着做老师布置的作业呢。现在只能布玛修雷达,悟空帮忙做作业了。
    作业是这样的,在数轴上有许多线段,每个线段都有一定的价值。现在给定一个区间[a,b],问该如何选取线段使得获取的价值最大,要求选取的线段必须在给定的区间范围内,并且不能互相重叠,仅端点相同不算重叠。

Input

第一行输入a,b,N,[a,b]为给定的区间,N(1<=N<=100)为线段数。
接下来N行,每行输入三个数p1,p2,v,其中p1,p2为线段的两个端点,v(-100<=v<=100)为线段的价值。其中,-5000<=a,b,p1,p2<=5000。

Output

输出一个数,即最大价值

Sample Input

-10 20 4
-5 5 20
3 10 30
8 20 50
10 20 30

Sample Output

70

Source
zzz
 
题目意思很好理解。方法也很好确定,动态规划。不过个人DP不是很懂。。以前做过的类似的题目现在居然没有想起来。看来还是知识点掌握的不够牢固啊、、。
代码如下:
 
#include <iostream>
#include <algorithm>
using namespace std;
struct Segment
{
 int s, e, value;
}a[101];
bool comp(const Segment &a, const Segment &b)
{
 return a.s < b.s;  
}
int main()
{
 int ss, ee, n, i, j = 0;
 cin >> ss >> ee >> n;
 for(i = 0; i < n; i++) 
 {
  int aa, bb, ww;
  cin >> aa >> bb >> ww;
  if(aa > bb){int temp = aa; aa = bb; bb = temp;}
  if(aa >= ss && bb <= ee && ww > 0)
  {
   a[j].s  = aa; a[j].e  = bb;  a[j].value = ww;
   ++j;
  }
 }
 n = j;
  sort(a, a + n, comp);
  int dp[101];
  for(i = 0; i < n; i++)
   dp[i] = a[i].value;
 int maxn = 0;
 for(i = 0; i < n; i++)
 {
  for(j = 0; j < i; j++)
  {
   if(a[i].s >= a[j].e && a[i].e <= ee && a[i].value + dp[j] > dp[i])
    dp[i] = a[i].value + dp[j];
  }
  if(dp[i] > maxn)
   maxn = dp[i];
 }
 cout << maxn << endl;
return 0;
}
  评论这张
 
阅读(223)| 评论(0)
推荐 转载

历史上的今天

评论

<#--最新日志,群博日志--> <#--推荐日志--> <#--引用记录--> <#--博主推荐--> <#--随机阅读--> <#--首页推荐--> <#--历史上的今天--> <#--被推荐日志--> <#--上一篇,下一篇--> <#-- 热度 --> <#-- 网易新闻广告 --> <#--右边模块结构--> <#--评论模块结构--> <#--引用模块结构--> <#--博主发起的投票-->
 
 
 
 
 
 
 
 
 
 
 
 
 
 

页脚

网易公司版权所有 ©1997-2017