#C241016A. 流浪地球

标签（Label）

• 动态规划
• 逆向思维

网址（Website）

题目详情 - 【NOIP模板】动态规划 - DP+二分查找 - 流浪地球 - Super

题解 - 【NOIP模板】动态规划 - DP+二分查找 - 流浪地球 - Super

题解（Solution）

$\qquad$在 AFO小技巧 里面有：若发现当前状态会影响到未来的状态，考虑逆向操作④。

代码（Code）

#include<bits/stdc++.h>
#include<vector>
#define For(i,l,r) for(int i=l;i<=r;i++)
#define Rof(i,l,r) for(int i=l;i>=r;i--)
using namespace std;
#define P pair<int,int>
#define int long long
#define x first
#define y second
inline int rd(){
	char c;bool f=false;while(!isdigit(c=getchar()))f=c=='-';int x=c^48;
	while(isdigit(c=getchar())){x=(((x<<2)+x)<<1)+(c^48);}return f?-x:x;
}const int inf = 0x3f3f3f3f3f3f3f3f;
const int N = 201234;
bool ST;

struct BIT{
	int n, c[N];
	inline void init(int x){n = x;memset(c,0,sizeof c);}
	void update(int x,int v){for(;x<=n;x+=x&-x)c[x]=max(c[x],v);}
	int ask(int x){int res=0;for(;x;x-=x&-x)res=max(res,c[x]);return res;}
}t;

int n,a[N],b[N],x[N],p[N],f[N];

void solve(){
	n = rd();For(i,1,n) a[i] = b[i] = rd(), p[i] = rd(), x[i] = rd();
	For(i,1,n) b[i+n] = a[i]+x[i]+1;
	sort(b+1,b+n*2+1);int cnt = unique(b+1,b+n*2+1)-b-1;
	t.init(cnt);
	For(i,1,n){
		int pos = lower_bound(b+1,b+cnt+1,a[i]) - b;
		f[i] = t.ask(pos) + p[i];
		pos = lower_bound(b+1,b+cnt+1,a[i]+x[i]+1) - b;
		t.update(pos, f[i]);
	}printf("%lld\n", t.ask(cnt));
}

bool ED;
signed main(){
	cerr<<abs(&ST-&ED)/1024./1024.<<"MB\n";
	int T = 1, Tim = clock();
	while(T--) solve();
	return cerr<<"TIME:"<<(clock()-Tim)/1000.,0;
}