转载请注明出处:http://tokitsukaze.live/

题目链接:http://acm.hdu.edu.cn/showproblem.php?pid=6447


题意:
从 (0,0) 往 (1e9,1e9)走,每次只能从 (x,y)走到 (x+1,y) 或者 (x,y+1)或者 (x+1,y+1)。某些点(x,y)有价值v,当且仅当从 (x−1,y−1)走到(x,y)时,才能获得v,求获得的价值总和最大是多少。


题解:
点只有1e5个。
dp[i]表示走到第i个点能获得的最大价值。
转移:dp[i]=max(dp[j])+v[i],需要满足条件x[j]<=x[i]-1且y[j]<=y[i]-1。

对x进行从小到大sort,然后扫描线扫过去。这样保证了转移的第一个条件。

对y离散化一下,开一个树状数组,下标表示y。每次通过树状数组查询前缀最大值进行dp转移。转移之后把dp值插入树状数组。这样保证了转移的第二个条件。

注意:因为x[j]<=x[i]-1,所以当x相同的时候,dp转移完不能马上插入树状数组,马上插入的话会导致转移条件变为x[j]<=x[i],这样就错了。所以当x相同的时候,我们先开个vector存放一下,等到碰到不同的x的时候,再全部一起插入。

代码:

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
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
#include <bits/stdc++.h>
using namespace std;
#pragma comment(linker, "/STACK:1024000000,1024000000")
#define mem(a,b) memset((a),(b),sizeof(a))
#define MP make_pair
#define pb push_back
#define fi first
#define se second
#define sz(x) (int)x.size()
#define all(x) x.begin(),x.end()
using namespace __gnu_cxx;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int,int> PII;
typedef pair<ll,ll> PLL;
typedef vector<int> VI;
typedef vector<ll> VL;
void go();
int main(){
#ifdef tokitsukaze
freopen("TEST.txt","r",stdin);
#endif
go();return 0;
}
const int INF=0x3f3f3f3f;
const ll LLINF=0x3f3f3f3f3f3f3f3f;
const double PI=3.1415926;
const double eps=1e-6;
const int MAX=1e5+10;
const ll mod=1e9+7;
/********************************* head *********************************/
struct Fenwick_Tree
{
#define type int
type bit[MAX];
int n;
void init(int _n){n=_n;mem(bit,0);}
int lowbit(int x){return x&(-x);}
void insert(int x,type v)
{
while(x<=n)
{
bit[x]=max(bit[x],v);
x+=lowbit(x);
}
}
type get(int x)
{
type res=0;
while(x)
{
res=max(res,bit[x]);
x-=lowbit(x);
}
return res;
}
#undef type
}tr;
struct node
{
int x,y,v;
node(){}
friend bool operator <(node a,node b){return a.x<b.x;}
void input(){read(x,y,v);}
}a[MAX];
int y[MAX];
void go()
{
int t,i,n,tot,ans;
read(t);
while(t--)
{
read(n);
for(i=0;i<n;i++)
{
a[i].input();
y[i]=a[i].y;
}
sort(a,a+n);
sort(y,y+n);
tot=unique(y,y+n)-y;
tr.init(tot+5);
ans=-INF;
VI tmp;
for(i=0;i<n;i++)
{
a[i].y=lower_bound(y,y+tot,a[i].y)-y+1;
if(sz(tmp)&&a[i].x!=a[tmp[0]].x)
{
for(auto &j:tmp) tr.insert(a[j].y+1,a[j].v);
tmp.clear();
}
a[i].v+=tr.get(a[i].y);
ans=max(ans,a[i].v);
tmp.pb(i);
}
printf("%d\n",ans);
}
}