为生存而奔跑

   :: 首页 :: 联系 :: 聚合  :: 管理
  271 Posts :: 0 Stories :: 58 Comments :: 0 Trackbacks

留言簿(5)

我参与的团队

搜索

  •  

积分与排名

  • 积分 - 319332
  • 排名 - 75

最新评论

阅读排行榜

评论排行榜

http://acm.hdu.edu.cn/showproblem.php?pid=2681
【题目】有n个节点,每个节点有一个s属性和一个t属性。现在要从中选出k个节点,满足:1、两个s属性的差值大于MAXK得节点不能同时选中。2、这k个节点的t的和最大。求出这个最大值。
【分析】枚举是否要选中第i个节点。假设要选中第i个节点,那么求出与第i个节点的s属性的差值不大于MAXK的所有节点,则这些节点中两两之间的s属性的值都不大于MAXK。枚举之前要先按s节点排序
#include<iostream>
#include
<cmath>
#include
<algorithm>
#define maxn 200+10
using namespace std;
class Girl
{
public:
    
int s,t;
    
bool operator <(const class Girl g)
    {
        
if(s==g.s)
            
return t<g.t;
        
return s<g.s;
    }
};
Girl girl[maxn];
int tmp[maxn];
bool cmp(const int & a,const int & b)
{
    
return a>b;
}
int main()
{
    
int n,k,MAXK;
    
int sum,ans;
    
int i,j,cnt;
    
while(scanf("%d%d%d",&n,&k,&MAXK)!=EOF)
    {
        ans
=0;
        
for(i=0;i<n;i++)
            scanf(
"%d%d",&girl[i].s,&girl[i].t);
        sort(girl,girl
+n);
        
for(i=0;i<n;i++)
        {
            tmp[
0]=girl[i].t;
            
for(j=i+1,cnt=1;j<n;j++)
                
if(girl[j].s-girl[i].s<=MAXK)
                    tmp[cnt
++]=girl[j].t;
            
if(cnt<k)
                
continue;
            sort(tmp,tmp
+cnt,cmp);
            
for(sum=j=0;j<cnt&&j<k;j++)
                sum
+=tmp[j];
            
if(j==&& sum>ans)
                ans
=sum;
        }
        printf(
"%d\n",ans==0?-1:ans);
    }
}

posted on 2009-08-13 15:41 baby-fly 阅读(131) 评论(0)  编辑 收藏 引用 所属分类: Algorithm

只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理