本帖最后由 善良的禽兽 于 2015-9-26 12:50 编辑
#include "cstdio"
#include "cmath"
#include "cstring"
#include "algorithm"
#include "iostream"
#include "vector"
#include "queue"
#include "stack"
#include "set"
#include "map"
#define lson root<<1
#define rson root<<1|1
#define lowbit(i) i&(-i)
#define debug(x) cout<<#x<<"="<<x<<endl;
#define here cout<<endl<<"_______________here "<<endl;
#define INF 0x7f7f7f7f
#define Prime 999983
#define N 1050
using namespace std;
typedef struct node
{
int s, e, va;
bool operator < (const node &o) const{
return e < o.e;
}
}node;
int dp[N];
node val[N];
int main()
{
#ifndef ONLINE_JUDGE
freopen("input.txt","r",stdin);
#endif
int n, m, r, maxx;
while(~scanf("%d%d%d", &n, &m, &r))
{
maxx = 0;
memset(dp, 0, sizeof(dp));
val[0].s = 0; val[0].e = -n; val[0].va = 0;
for(int i = 1; i <= m; i++)
scanf("%d%d%d", &val.s, &val.e, &val.va);
sort(val, val + m + 1);
for(int i = 1; i <= m; i++)
{
for(int j = 0; j < i; j++)
{
if(val.s - val[j].e >= r)
dp = max(dp, dp[j] + val.va);
}
}
for(int i = 1; i <= m; i++)
maxx = max(maxx, dp);
printf("%d\n", maxx);
}
return 0;
}
#include "cstdio"
#include "cmath"
#include "fstream"
#include "cstring"
#include "algorithm"
#include "iostream"
#include "vector"
#include "queue"
#include "stack"
#include "set"
#include "map"
#define lson root<<1
#define rson root<<1|1
#define lowbit(i) i&(-i)
#define debug(x) cout<<#x<<"="<<x<<endl;
#define here cout<<endl<<"_______________here "<<endl;
#define INF 0x7f7f7f7f
#define LINF 0x7f7f7f7f7f7f7f7f
#define Prime 999983
#define N 1000500
using namespace std;
typedef struct node
{
int s, e, value;
bool operator < (const struct node &o)const{
if(e == o.e){
if(s == o.s)
return value > o.value;
return s < o.s;
}else{
return e < o.e;
}
}
}node;
struct
{
int s, e;
long long maxx;
}tree[N<<2];
node state[1050];
void buildtree(int root, int s, int e)
{
tree[root].s = s;
tree[root].e = e;
tree[root].maxx = 0;
if(s == e)
return ;
int mid((s + e)>>1);
buildtree(lson, s, mid);
buildtree(rson, mid + 1, e);
}
void Insert(int root, int pos, long long t)
{
if(tree[root].s == tree[root].e)
{
tree[root].maxx = max(t, tree[root].maxx);
return ;
}
int mid((tree[root].s + tree[root].e)>>1);
if(pos <= mid)
Insert(lson, pos, t);
else
Insert(rson, pos, t);
tree[root].maxx = max(tree[lson].maxx, tree[rson].maxx);
}
long long query(int root, int s, int e)
{
if(s <= tree[root].s && tree[root].e <= e)
return tree[root].maxx;
int mid((tree[root].s + tree[root].e)>>1);
if(e <= mid){
return query(lson, s, e);
}else if(mid < s){
return query(rson, s, e);
}else{
return max(query(lson, s, mid), query(rson, mid + 1, e));
}
}
int main()
{
#ifndef ONLINE_JUDGE
freopen("input.txt","r",stdin);
#endif
int n, m, relax, best;
while(~scanf("%d%d%d", &n, &m, &relax))
{
for(int i = 0; i < m; i++)
{
scanf("%d%d%d", &state.s, &state.e, &state.value);
state.s++; state.e++;
}
sort(state, state + m);
buildtree(1, 0, n);
for(int i = 0; i < m; i++)
{
if(state.s - relax >= 0)
best = query(1, 0, state.s - relax);
else
best = 0;
//printf("s = %d, e = %d, value = %d, best = %d\n", state.s, state.e, state.value, best);
if(state.e <= n + 1)
Insert(1, state.e, state.value + best);
}
printf("%lld\n", query(1, 0, n + 1));
}
return 0;
}
|
|
收藏
淘帖
踩
