nowcoder941B 弹钢琴

题目链接

思路

首先按照音色排个序，顺便离散化一下音高。
用\(h[i]\)表示第\(i\)个键的音高,用\(w[i]\)表示第\(i\)个键的春希度。
朴素\(dp\)
\(f[i][j]\)表示前i个琴键，最高的音高为j时的最大收益。
那么当\(j\)大于\(h[i]\)时，就有\(f[i][j] = max(f[i-1][j],f[i-1][a[i]] + w[i])\)
否则就\(f[i][j] = f[i - 1][j]\)

优化

显然可以用树状数组优化(维护一个区间赋值和区间求最大值的操作)。

教训

发现了自己离散化的姿势是存在问题的！！
之前一直用\(map\)离散化，数据比较小了还体现不出来，数据比较大的时候就要比\(lower_bound\)慢很多。
对比

代码

/*
* @author: wxyww
* @date:   2019-06-28 19:59:57
* @last modified time: 2019-06-29 15:45:15
*/
#include<cstdio>
#include<iostream>
#include<cstdlib>
#include<cstring>
#include<algorithm>
#include<queue>
#include<vector>
#include<ctime>
#include<map>
using namespace std;
typedef long long ll;
const int n = 1000000 + 100;
map<int,int>ma;
ll read() {
    ll x=0,f=1;char c=getchar();
    while(c<'0'||c>'9') {
        if(c=='-') f=-1;
        c=getchar();
    }
    while(c>='0'&&c<='9') {
        x=x*10+c-'0';
        c=getchar();
    }
    return x*f;
}
int ls[n];
struct node {
    int x,y;int w;
}a[n];
int js;
ll tree[n];

void update(int pos,ll w) {
    while(pos <= js) {
        tree[pos] = max(tree[pos],w);
        pos += pos & -pos;
    }
}
ll query(int pos) {
    ll ret = 0;
    while(pos) {
        ret = max(ret,tree[pos]);
        pos -= pos & -pos;
    }
    return ret;
}
bool cmp(const node &a,const node &b) {
    return a.x == b.x ? a.y < b.y : a.x < b.x;
}
int main() {
    int n = read();
    for(int i = 1;i <= n;++i) a[i].x = read() + 1,ls[i] = a[i].y = read() + 1,a[i].w = read();
    sort(ls + 1,ls + n + 1);
    sort(a + 1,a + n + 1,cmp);
    js = n;
    for(int i = 1;i <= n;++i)
        a[i].y = lower_bound(ls + 1,ls + n + 1,a[i].y) - ls;

    for(int i = 1;i <= n;++i) {
        ll x = query(a[i].y) + a[i].w;
        update(a[i].y,x);
    }
    cout<<query(js);
    return 0;
}