题目描述

Description

Input

第一行是用空格隔开的二个正整数，分别给出了舞台的宽度W（1到10^8之间）和馅饼的个数n（1到10^5）。　　接下来n行，每一行给出了一块馅饼的信息。由三个正整数组成，分别表示了每个馅饼落到舞台上的时刻t[i]（1到10^8秒），掉到舞台上的格子的编号p[i]（1和w之间），以及分值v[i]（1到1000之间）。游戏开始时刻为0。输入文件中同一行相邻两项之间用一个空格隔开。输入数据中可能存在两个馅饼的t[i]和p[i]都一样。

Output

一个数，表示游戏者获得的最大总得分。

Sample Input

3 4
1 2 3
5 2 3
6 3 4
1 1 5

Sample Output

12

【数据规模】

对于100%的数据，1<=w,t[i]<=10^8,1<=n<=100000。

题目分析

dp[i]表示第i个馅饼被收集时可以获得的最大分数

需要满足：
将第二个条件拆开 移项变成

然后把最后两个条件加和，移项 可以得到
发现如果满足了后两个条件，一定会得到这个条件，也一定会满足第一个条件。
好的 后两个条件一个排序 一个离散化用树状数组维护即可

#include <cstdio>
#include <cstring>
#include <set>
#include <map>
#include <vector>
#include <cmath>
#include <queue>
#include <algorithm>
using namespace std;
int n;
struct your
{
    int t,p;
    int x,y;
    int val;
}a[100010];
int cmp(your j,your k)
{
    return j.x<k.x;
}
int cmp2(your j,your k)
{
    return j.y<k.y;
}
int cnt,ans;
int c[100010];
int f[1000010];
int dp[100010];
void update(int x,int c)
{
    for(;x<=cnt;x+=x&-x) f[x]=max(f[x],c);
}
int ask(int x)
{
    int sum=0;
    for(;x;x-=x&-x) sum=max(sum,f[x]);
    return sum;
}
int main()
{   
    scanf("%*d%d",&n);
    for(int i=1;i<=n;i++)
        scanf("%d%d%d",&a[i].t,&a[i].p,&a[i].val),a[i].x=a[i].t*2+a[i].p,a[i].y=a[i].t*2-a[i].p;
    sort(a+1,a+n+1,cmp);
    for(int i=1;i<=n;i++)
    {
        if(a[i].x!=a[i-1].x) cnt++;
        c[i]=cnt;
    }
    for(int i=1;i<=n;i++) a[i].x=c[i];
    sort(a+1,a+n+1,cmp2);
    for(int i=1;i<=n;i++)
    {
        dp[i]=ask(a[i].x)+a[i].val;
        ans=max(ans,dp[i]);
        update(a[i].x,dp[i]);
    }   
    printf("%d",ans);
    return 0;   
}