[CSP-S模拟测试]:数对（线段树优化DP）

题目传送门（内部题96）

输入格式

　　第一行一个整数$n$，接下来$n$行每行三个整数$a_i,b_i,w_i$。

输出格式

　　一行一个整数表示最大权值和。

样例

样例输入：

5
4 4 1
2 3 3
1 5 1
4 2 2
5 2 3

样例输出：

数据范围与提示

　　对于$10\%$的数据，$n\leqslant 8$。
　　对于$40\%$的数据，$n\leqslant 200$。
　　对于$70\%$的数据，$n\leqslant 3,000$。
　　对于$100\%$的数据，$1\leqslant n\leqslant 10^5 ,1\leqslant a_i,b_i,w_i\leqslant 10^9$。

题解

先来考虑如何选择最优，按$a_i+b_i$从小到大排序和按$min(a_i,b_i)$从小到大排序都能通过此题（我也不知道为什么）。

发现$a_i,b_i$只与其大小有关，而与其具体值无关，所以直接离散化就好了。

考虑$DP$，定义$dp[i][j]$表示选到第$i$个，$\min(a_i)$为$j$的最大贡献。

可以写出转移：

$$dp[i][j]=\max(dp[i-1][j])$$

$$dp[i][\max(j,a[i])]=\max(dp[i-1][j]+w[i])$$

显然无论是空间还是时间都不能容忍，考虑优化。

发现其实就是一个区间加的过程，于是可以用线段树优化。

时间复杂度：$\Theta(n\log cnt)$（其中$cnt$为不同的$a_i$和$b_i$的种数）。

期望得分：$100$分。

实际得分：$100$分。

代码时刻

#include<bits/stdc++.h>

#define L(x) x<<1

#define R(x) x<<1|1

using namespace std;

unordered_map<int,int>mp;

struct rec{int a,b,w;}e[100001];

int n;

int cnt;

int que[200001];

long long tr[1000000],lz[1000000];

bool cmp(rec a,rec b){return a.a+a.b<b.a+b.b;}

void pushup(int x){tr[x]=max(tr[L(x)],tr[R(x)]);}

void pushdown(int x)

{

	tr[L(x)]+=lz[x];

	tr[R(x)]+=lz[x];

	lz[L(x)]+=lz[x];

	lz[R(x)]+=lz[x];

	lz[x]=0;

}

void add(int x,int l,int r,int L,int R,int w)

{

	if(r<L||R<l)return;

	if(L<=l&&r<=R)

	{

		tr[x]+=w;

		lz[x]+=w;

		return;

	}

	int mid=(l+r)>>1;

	pushdown(x);

	add(L(x),l,mid,L,R,w);

	add(R(x),mid+1,r,L,R,w);

	pushup(x);

}

void upd(int x,int l,int r,int k,long long w)

{

	if(l==r)

	{

		tr[x]=max(tr[x],w);

		return;

	}

	int mid=(l+r)>>1;pushdown(x);

	if(k<=mid)upd(L(x),l,mid,k,w);

	else upd(R(x),mid+1,r,k,w);

	pushup(x);

}

long long ask(int x,int l,int r,int L,int R)

{

	if(r<L||R<l)return -0x3f3f3f3f3f3f3f3f;

	if(L<=l&&r<=R)return tr[x];

	int mid=(l+r)>>1;pushdown(x);

	return max(ask(L(x),l,mid,L,R),ask(R(x),mid+1,r,L,R));

}

int main()

{

	scanf("%lld",&n);int top=0;

	for(int i=1;i<=n;i++)

	{

		scanf("%d%d%d",&e[i].a,&e[i].b,&e[i].w);

		que[++top]=e[i].a;que[++top]=e[i].b;

	}

	sort(que+1,que+top+1);

	for(int i=1;i<=top;i++)if(que[i]!=que[i-1])mp[que[i]]=++cnt;

	for(int i=1;i<=n;i++){e[i].a=mp[e[i].a];e[i].b=mp[e[i].b];}

	sort(e+1,e+n+1,cmp);

	for(int i=1;i<=n;i++)

	{

		long long flag=ask(1,1,cnt,1,min(e[i].a,e[i].b));

		add(1,1,cnt,e[i].a,e[i].b,e[i].w);

		upd(1,1,cnt,e[i].a,flag+e[i].w);

	}

	printf("%lld",tr[1]);

	return 0;

}

rp++

巴特西