(Zj) b903: 高中組-第九題：超級電池

http://zerojudge.tw/ShowProblem?problemid=b903

我首殺耶，開心XD

74% 解法：dp[i][j]代表選前i個超級石和前j個鑰石所得最大的能力值是多少，然後用類似LCS的更新手法，O(n^2)

100% 解法：先把K個配對按照 "超級石" 的大小排序，之後開一個dp陣列，dp[i]代表說，如果最後用了第i個 "鑰石" ， 所能獲得最大的點數是多少。那更新dp陣列的轉移方程就是(假設現在超級石編號為a，鑰石編號為b，能力值為c)dp[b] = max(dp[1~b-1] + c,dp[b])，那，我們可以用segment tree來維護dp陣列，這樣複雜度就可以壓到O(n lg n)

#include <iostream>
#include <stdio.h>
#include <utility>
#include <algorithm>
using namespace std;

typedef long long LL;
typedef pair<LL,LL> pii;
typedef pair<pii,LL> piii;
const int MAX_N = 3e5 + 6;
const LL INF = 1e17+6;

struct Node {
    Node* lc;
    Node* rc;
    LL val;
    Node() {
        lc=rc=NULL;
        val = 0;
    }
};

LL pull(LL lc,LL rc) {
    return max(lc,rc);
}

Node* Build(int L,int R) {
    Node* node =new Node();
    if (L==R) {
        return node;
    }
    int mid=(L+R)>>1;
    node->lc=Build(L,mid);
    node->rc=Build(mid+1,R);
    return node;
}

void modify(Node* node,int L,int R,int pos,LL val) {
    if (L==R) {
        node->val = val;
        return;
    }
    int mid=(L+R)>>1;
    if (pos<=mid) modify(node->lc,L,mid,pos,val);
    else modify(node->rc,mid+1,R,pos,val);
    node->val = pull(node->lc->val,node->rc->val);
    return;
}

LL query(Node* node,int L,int R,int l,int r) {
    if (L>r || l>R) return 0;
    else if (l<=L && R<=r) return node->val;
    int mid=(L+R)>>1;
    return pull(query(node->lc,L,mid,l,r),query(node->rc,mid+1,R,l,r));
}

piii ipt[MAX_N];

int main () {
    int n,m,k;
    while (scanf("%d %d %d",&n,&m,&k) != EOF) {
        for (int x=1;k>=x;x++) {
            int i,j,k;
            scanf("%d %d %d",&i,&j,&k);
            ipt[x] = make_pair(make_pair(i,-j),k);
        }
        sort(ipt+1,ipt+k+1);
        Node* root = Build(1,m);
        for (int x=1;k>=x;x++) {
            int i=ipt[x].first.first,j=-ipt[x].first.second,k=ipt[x].second;
            LL t=query(root,1,m,1,j-1);
            modify(root,1,m,j,max(query(root,1,m,j,j),t+k));
        }
        printf("%lld\n",root->val);
    }
}