Zhejiang University of Technology Freshman Competition E DD_2020 BOND Buy Cyberpunk 2077

Note: This article is still in the EA stage and needs to be corrected and improved urgently

Last updated: 2021/11/10 0:17

Note: The code in this article can be AC, but the explanation may be incorrect. The idea is for reference only.

Dynamic Planning + Segment Tree

Reference resources:

Cyberpunk 2077 Purchase Link (Fog) https://store.steampowered.com/app/1091500/_2077/

Title Description
Today, I watched the DD_after the Cyberpunk 2077 trial BOND, decided to buy it and buy it!! After looking at its price of 298, DD_BOND looked at his balance and wondered if there was a cheaper way to buy it. Coincidentally, when DD_ When BOND opened steam, he found that G Pang was on sale and needed only 298298 different points to exchange for Cyberpunk 2077.
Now there are m gift packs in the store. The first one costs v[i]. The gift pack contains all the points of l[i]~r[i], DD_BOND is a fool. Ask for help and tell him how much it will cost to collect all the points from 1 to 298298. If not, tell him-1.

An integer m (1<=m<=1e5) indicates that there are m gift packages followed by M lines, each with l[i],r[i],v[i] (1<=l[i]<=r[i]<=r[i]<=298298, 0<=v[i]<=1e9) indicating the number of points the package contains and the price of the package.
If all points from 1 to 298298 cannot be output-1, otherwise the minimum total price will be output.

sample input
[Sample 1 input]

1 2077 1
2078 298298 2
2 298298 3

[Sample 2 Input]

1 2077 1
2078 298297 3
2 21233 5

sample output
[Sample 1 Output]


[Sample 2 Output]


Title Analysis:

1. Summary of Title (from reference link 1)
Given n n n n n n n n intervals, each interval has three values l,r,v, V indicating that the cost of V can cover the interval [l,r], and the minimum cost of the coverage interval [1,298298]

2. Solving problems with dynamic programming

(1) Defining the meaning of dp[]
dp[i] is defined as the minimum cost to have the first I points
Then dp[298298] is the answer to this question (actually dp[298298+1] is the answer because of the use of a segment tree, which is mentioned in the code comment)

(2) Find out the relationship between dp[] (this part needs to be improved, you can take a look at 2333 first)
First, each interval is sorted in ascending order by the right endpoint, and ascending order by the left endpoint if the right endpoint is the same
Then iterate through each interval from scratch. For the current interval l,r,v, we can move from dp[j] (l-1<=j<=r) to the current dp[k] (l<=k<=r), that is

dp[r]=min(dp[r],dp[l-1 -> r]+v)

(3) Find the initial conditions
Specifies that the initial value of dp[] is a large number of INF s
Where dp[0]=0 (where the array subscript is moved one bit to the right in the code, in fact dp[1]=0)

3. Simulating Array dp[] with Segment Tree
See the code for details, which will be improved later (not necessarily)

The AC code is as follows

The code comes from the above three reference links, and I supplement the full-text notes with my own understanding, pointing out any errors in time

The original code uses fast read-in and built-in comparison functions within the structure to speed up the program. To simplify the code, I used a simpler and more violent method (the cmp() parameter of cin and sort())

#define ll long long
#define Inf 0x3f3f3f3f3f3f3f3f
using namespace std;
const int maxn = 3e5+5;
struct node{//Structures store each interval 
	int l,r;
	long long val;

bool cmp(node x,node y){//Functions required for structure sort() 
	if(x.r==y.r) return x.l<y.l;
	else return x.r<y.r;//Sort intervals in ascending order by right endpoint, same right endpoint in ascending order by left endpoint 

/*-----Below is the segment tree section-----*/ 

ll n,a[maxn<<2];//Array stores segment trees, four times larger 
//x*2 is equivalent to x< < 1 
//x*4 is equivalent to x< < 2 
//x*2+1 is equivalent to x< < 1|1 

void pushup(int root){//Update node information, here is the minimum value for left and right child nodes 
	//Root*2 is the lower left node and root*2+1 is the lower right node 

void build(int root,int l,int r){//Build Trees
	//root is the corresponding subscript of the current node at a[], that is, the actual storage location 
	//[l,r] denotes the current node interval 
	if(l==r){//Arrive at leaf node 
		//The initialization node value is Inf, which is used to compare the minimum value while participating in determining whether all Steam points are covered  
		return ;
	int mid=l+r>>1;//Left and right recursion, equivalent to min=(l+r)/2 
	build(root<<1  ,l    ,mid);
	build(root<<1|1,mid+1,r  );
	pushup(root);//Recursion complete, update this node information 
void update(int root,int l,int r,int pos,ll val){//Point Modification 
	//root,l,r have the same meaning as above
	//pos is the actual subscript pos < [1,298298+1] of the array dp expressed by the segment tree 
	//Value is the value you want to modify to 
	if(l==r){//Arrive at leaf node 
		a[root]=min(a[root],val);//Modify to Minimum 
		return ;
	int mid=l+r>>1;
	//Decide whether you need to go left or right, from top to bottom, to leaf nodes 
	if(pos<=mid) update(root<<1,l,mid,pos,val);
	else update(root<<1|1,mid+1,r,pos,val);
	//Recursively (walk) through updating this node's information 
ll query(int root,int l,int r,int ql,int qr){//Interval Query 
	if(l>qr || r<ql) return Inf;
	//The query is out of range [ql,qr] and has no cross-sections. Also participates in determining if all Steam points are covered  
	else if(l>=ql && r<=qr) return a[root];//Return values directly within an interval 
	else{//Has crossover, recursively to crossover, returns the value of crossover 
		int mid=l+r>>1;
		return min(query(root<<1,l,mid,ql,qr),query(root<<1|1,mid+1,r,ql,qr));
int main(){
	for(int i=0;i<n;i++){
		//Since segment tree habits are established from 1, and nod[i].l-1 equals 0 when l=1, move all intervals one bit to the right 
	/*Below is the segment tree section*/ 
	//Segment Tree Analog Array dp[1 -> 298298+1] 
	build(1,1,maxn);//Build Trees
	update(1,1,maxn,1,0);//The dp[1] simulated by the segment tree is given an initial value of 0 
	/*---This for loop below has an equivalent code to refer to later -.*/ 
	for(int i=0;i<n;i++){
		ll minn=query(1,1,maxn,nod[i].l-1,nod[i].r);//Query dp[l-1 -> r] Minimum 
		minn+=nod[i].val;//Minimum plus new value 
		update(1,1,maxn,nod[i].r,minn);//Equivalent to dp[nod[i].r]=minn 
	ll ans=query(1,1,maxn,298298+1,298298+1);//Query the array dp[298298+1] simulated by the segment tree 
	if(ans!=Inf) cout<<ans;
	else cout<<-1;
	return 0;

Keywords: Algorithm Dynamic Programming

Added by ASDen on Tue, 09 Nov 2021 19:26:54 +0200