https://atcoder.jp/contests/abc266/tasks
Ex - Snuke Panic (2D)
N个点会出现, 第i个,在ti时刻出现在(xi,yi), 大小为ai
Takahashi 0时刻在 (0,0)
一单位时间
方案1: 可以x 正向/负向移动1
方案2: y正向移动1
方案3: 不移动
恰好在ti时刻在xi,yi则可获得ai
求可获得的ai的总和的最大值
范围
n 1e5
ti 1e9
xi,yi [0,1e9]
ai [1,1e9]
5s 1024mb
我的思路
不妨把点按照时间ti排序
dp[i] = 要获得i, 前ti能得到的最大值, 显然有局部性,
dp[i] = a[i] + max(dp[j]), yj<=yi, abs(xi-xj)+(yi-yj) <= ti-tj
对限制进行处理
abs(xi-xj)+(yi-yj) <= ti-tj 去掉abs
xi-xj+(yi-yj) <= ti-tj 且 xj-xi+(yi-yj) <= ti-tj
分离i,j
ti-xi-yi >= tj-xj-yj 且 ti+xi-yi >= tj+xj-yj
也就是 (yi,ti-xi-yi,ti+xi-yi) 三维偏序中 最大的dp[j]
然而并不会去做三维偏序的
甚至二维偏序也不太会写
题解
一样的也是三维偏序
但实际上这里并不需要t !!!
因为如果无法达到, 则直接忽略
而 i -> j 可达 等价于 3维偏序的满足, 已经说明了 t[i]< t[j], !!!
所以干掉t以后, 就可以按y排序(另外两个也行), 反正其中一个排序,剩下就是二维偏序了
代码
https://atcoder.jp/contests/abc266/submissions/35639063
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
| #include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define rep(i,a,n) for (ll i=a;i<(ll)n;i++)
#define per(i,a,n) for (ll i=n;i-->(ll)a;)
#define pb push_back
ll read(){ll r;scanf("%lld",&r);return r;}
struct BIT{
int n;
unordered_map<int,ll>data;
BIT():n(0){};
BIT(int N):n(N){};
void set(int i,ll val){
for(i++;i<=n;i+=i&-i)data[i-1]=max(data[i-1],val);
}
ll prod(int i){
ll ans=0;
for(;i;i-=i&-i)ans=max(ans,data[i-1]);
return ans;
}
};
struct BIT2D{
int h,w;
vector<BIT>data;
BIT2D(int H,int W):h(H),w(W),data(h,BIT(w)){};
void set(int i,int y,ll val){
for(i++;i<=h;i+=i&-i) data[i-1].set(y,val);
}
ll prod(int i,int j){
ll ans=0;
for(;i;i-=i&-i)ans=max(ans,data[i-1].prod(j));
return ans;
}
};
int main(){
int n=read();
vector<array<int,4>>data;
vector<int>P,Q;
rep(i,0,n){
int t=read();
int x=read();
int y=read();
int a=read();
if(t>=abs(x)+y){
data.push_back({y,t-x-y,t+x-y,a});
P.push_back(t-x-y);
Q.push_back(t+x-y);
}
}
sort(data.begin(),data.end());
P.push_back(0);
sort(P.begin(),P.end());
P.erase(unique(P.begin(),P.end()),P.end());
Q.push_back(0);
sort(Q.begin(),Q.end());
Q.erase(unique(Q.begin(),Q.end()),Q.end());
BIT2D bit2d(P.size(),Q.size());
auto fp=[&](int x){return lower_bound(P.begin(),P.end(),x)-P.begin();};
auto fq=[&](int y){return lower_bound(Q.begin(),Q.end(),y)-Q.begin();};
ll ans=0;
for(auto query:data){
auto[y,p,q,val]=query;
p=fp(p);
q=fq(q);
ll ret=bit2d.prod(p+1,q+1);
ans=max(ans,ret+val);
bit2d.set(p,q,ret+val);
}
printf("%lld\n",ans);
}
|
总结
现场做了, 推出了Ex是个三维偏序,但不会写..
Ex
一个是没发现这里 的t可以干掉, 这样3维可以控制顺序变成二维!!!
有道理啊, 学会了2d fenwick
因为相当于 (i,j) 只会写入 log(H)log(W)个位置, 那么n个点, 就只有 n log^2
所以即使是3维也可以搞
只需要内部用unordered_map 而不是vector,就可以解决空间了
参考
官方题解