Buy and Resell
题意：
有一个物品有(n)个价格，从(1)到(n)遍历，对于每个价格(a[i])，可以花(a[i])购买，或者把现在拥有的物品以(a[i])的价格卖出赚取差价，或者什么都不做，问最终能获得的最大收益以及最大收益下的最小交易次数
思路：
遍历过程中维护一个集合，表示当前可以获得的(a[i])的值（不一定是已经获得的），这些可以获得的(a[i])可能有两种来源，一种就是花钱买的，一种是用集合里的值换的。
对于新的(a[i])，如果小于等于集合里最小值，那就加入集合，因为亏本，所以不可能换，这里是花钱买的。
否则，我们就用最小的值把(a[i])换进来，并把差值加进(ans)里，这时(a[i])可以有上述两种来源，所以把(a[i])加入集合两次，并打标记区分，此时原来的最小值已经被换出，不在集合中了
对于交易次数，每次换出最小值时判断这个值是否是买进来的，是的话交易次数(+2)
集合中被标记为换来的值其实相当于一个暂时的替代品，一个中介，比如(a)换(b)，(b)换(c)，其实最终就是(a)换(c)，(b)只是一个中介
每次换出最小值，其实一次交易（买入卖出）并没有完成，因为被标记为换入的(a[i])可能成为最小值被换出，这个操作就延续的原来的交易
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn = 100010;
struct s{
int v, mk;
friend bool operator < (s x, s y){
if(x.v != y.v)
return x.v > y.v;
return x.mk > y.mk;
}
};
int a[maxn];
int main(){
ios::sync_with_stdio(false);
cin.tie(nullptr);
int t, n;
cin >> t;
while(t--){
cin >> n;
for(int i = 1; i <= n; ++i) cin >> a[i];
priority_queue<s>q;
ll ans = 0, cnt = 0;
for(int i = 1; i <= n; ++i){
if(q.empty()) q.push(s{a[i], 1});
else{
auto x = q.top();
if(x.v >= a[i])
q.push(s{a[i], 1});
else{
ans += a[i] - x.v;
q.pop();
q.push(s{a[i], 1});
q.push(s{a[i], 0});
if(x.mk) cnt += 2;
}
}
}
cout << ans << ' '<< cnt <<'
';
}
return 0;
}
YJJ's Salesman
题意：
二维平面上(n)个点，每个点有权值，从((0,0))到((1e9,1e9))，每次移动只能从((x,y))到((x+1,y))或者((x,y+1))或者((x+1,y+1))，且只有通过第三种方式到达某个点才能获得该点的权值，问能获得的最大权值
思路：
(dp[i][j] = max(dp[i-1][j], dp[i][j-1], dp[i-1][j-1] + v[i][j]))
但是数据太大，考虑优化
只考虑有权值的(n)个点，对于每个点，状态从该点左下方的最大值转移过来
所以对于每个点，答案就是左下方的矩形((0,0)-(x-1,y-1))和该点权值之和，遍历(n)个点取最大即为答案
先对(n)个点的纵坐标离散化，然后按横坐标升序，纵坐标降序排列，每个点把纵坐表插入树状数组求前缀最大值
对于当前的点((x,y))，先查询树状数组中前缀([1,y-1])的最大值，此时统计的恰好是矩形((0,0)-(x-1,y-1))
因为对于树状数组中大于等于(y)的值不影响查询结果，而小于(y)且大于等于(x)的值还没插入，这就是同一横坐标要从上往下处理的原因
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn = 100010;
struct s {
int x, y, v;
friend bool operator<(s a, s b) {
if (a.x == b.x) return a.y > b.y;
return a.x < b.x;
}
} a[maxn];
int n, t;
ll mx[maxn];
void add(int x, ll val) {
for (int i = x; i <= n; i += i & (-i))
mx[i] = max(mx[i], val);
}
ll ask(int x) {
ll ans = 0;
for (int i = x; i >= 1; i -= i & (-i))
ans = max(ans, mx[i]);
return ans;
}
vector<int> vec;
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
cin >> t;
while (t--) {
memset(mx, 0, sizeof(mx));
vec.clear();
cin >> n;
for (int i = 1; i <= n; ++i) {
cin >> a[i].x >> a[i].y >> a[i].v;
vec.push_back(a[i].y);
}
sort(vec.begin(), vec.end());
vec.erase(unique(vec.begin(), vec.end()), vec.end());
for (int i = 1; i <= n; ++i)
a[i].y = lower_bound(vec.begin(), vec.end(), a[i].y) - vec.begin() + 1;
sort(a + 1, a + 1 + n);
ll ans = 0;
for (int i = 1; i <= n; ++i) {
ll x = ask(a[i].y - 1) + a[i].v;
ans = max(ans, x);
add(a[i].y, x);
}
cout << ans << '
';
}
return 0;
}