Growth(预处理+记忆化搜索)

题目：

弱弱有两个属性a和b，这两个属性初始的时候均为0，每一天他可以通过努力，让a涨1点或b涨1点。
为了激励弱弱努力学习，我们共有n种奖励，第i种奖励有xi，yi，zi三种属性，若a≥ xi且b≥ yi，则弱弱在接下来的每一天都可以得到zi的分数。
问m天以后弱弱最多能得到多少分数。
数据范围：
第一行一个两个整数n和m（1≤ n≤ 1000，1≤ m≤ 2000000000）。
接下来n行，每行三个整数xi，yi，zi（1≤ xi,yi≤ 1000000000，1≤ zi ≤ 1000000）。

做法：

先将属性a的xi和属性b的yi离散化，分开离散化。
然后预处理：
当然这个i和j是离散化后的xi和yi，也就是将xi排序后第i大的xi和将yi排序后第j大的值，不然数组开不下。
这个东西我们开n个树状数组来维护一下就行。
设：
那么dp[1][1]就是我们要的答案。
转移：

终态：

代码：

#include <bits/stdc++.h>
#define debug(a) cout << #a ": " << a << endl
#define IOS ios::sync_with_stdio(false), cin.tie(0)
using namespace std;
typedef long long ll;
const int N = 1010;
const int inf = 2e9+7;
int n, m, a[N], b[N], c[N];
vector<int> h1, h2;
int tot1, tot2;
ll T[N][N], dp[N][N];
int get(vector<int>& h, int x){
    return lower_bound(h.begin(), h.end(), x)-h.begin()+1;
}
int lowbit(int x){
    return x&(-x);
}
void add(int id, int x, int y){
    for (int i = x; i <= tot2; i += lowbit(i)) T[id][i] += y;
}
ll ask(int id, int x){
    ll ans = 0;
    for (int i = x; i >= 1; i -= lowbit(i)) ans += T[id][i];
    return ans;
}
ll dfs(int x, int y){
    if (dp[x][y] != -1) return dp[x][y];
    ll now_x = h1[x-1], now_y = h2[y-1];
    ll nxt_x = x == tot1 ? inf : h1[x];
    ll nxt_y = y == tot2 ? inf : h2[y];
    ll& ans = dp[x][y] = 0;
    if (nxt_x+now_y > m && nxt_y+now_x > m){
        ans = ask(x, y)*(m-(now_x+now_y)+1);
    }
    if (nxt_x+now_y <= m){
        ans = max(ans, ask(x, y)*(nxt_x-now_x)+dfs(x+1, y));
    }
    if (nxt_y+now_x <= m){
        ans = max(ans, ask(x, y)*(nxt_y-now_y)+dfs(x, y+1));
    }
    return ans;
}
int main(void){
    IOS;
    cin >> n >> m;
    for (int i = 1; i <= n; ++i){
        cin >> a[i] >> b[i] >> c[i];
        h1.push_back(a[i]);
        h2.push_back(b[i]);
    }
    sort(h1.begin(), h1.end());
    h1.erase(unique(h1.begin(), h1.end()), h1.end());
    sort(h2.begin(), h2.end());
    h2.erase(unique(h2.begin(), h2.end()), h2.end());
    tot1 = h1.size(), tot2 = h2.size();
    for (int i = 1; i <= n; ++i){
        for (int j = get(h1, a[i]); j <= tot1; ++j){
            add(j, get(h2, b[i]), c[i]);
        }
    }
    memset(dp, -1, sizeof dp);
    cout << dfs(1, 1) << endl;
    return 0;
}