http://acm.hdu.edu.cn/showproblem.php?pid=2681【題目】有n個節(jié)點，每個節(jié)點有一個s屬性和一個t屬性。現(xiàn)在要從中選出k個節(jié)點，滿足：1、兩個s屬性的差值大于MAXK得節(jié)點不能同時選中。2、這k個節(jié)點的t的和最大。求出這個最大值。
【分析】枚舉是否要選中第i個節(jié)點。假設(shè)要選中第i個節(jié)點，那么求出與第i個節(jié)點的s屬性的差值不大于MAXK的所有節(jié)點，則這些節(jié)點中兩兩之間的s屬性的值都不大于MAXK。枚舉之前要先按s節(jié)點排序
#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==k && sum>ans)
ans=sum;
}
printf("%d\n",ans==0?-1:ans);
}
}