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:
https://blog.csdn.net/qq_39641976/article/details/111195335
https://blog.csdn.net/zearot/article/details/52280189
https://blog.csdn.net/zearot/article/details/48299459
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.
input
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.
output
If all points from 1 to 298298 cannot be output-1, otherwise the minimum total price will be output.
sample input
[Sample 1 input]
3 1 2077 1 2078 298298 2 2 298298 3
[Sample 2 Input]
3 1 2077 1 2078 298297 3 2 21233 5
sample output
[Sample 1 Output]
3
[Sample 2 Output]
-1
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
(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())
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
#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;
}nod[maxn];
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
a[root]=min(a[root<<1],a[root<<1|1]);
//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
a[root]=Inf;
//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
pushup(root);
}
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(){
cin>>n;
for(int i=0;i<n;i++){
cin>>nod[i].l>>nod[i].r>>nod[i].val;
nod[i].l++;nod[i].r++;
//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
}
sort(nod,nod+n,cmp);
/*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;
}