fork download
copy 
  1. #include <bits/stdc++.h>
  2.  
  3. #define el '\n'
  4. #define fi first
  5. #define sec second
  6. #define pb push_back
  7. #define ll long long
  8. #define sz(v) (int)(v).size()
  9. #define all(v) (v).begin(),(v).end()
  10.  
  11. using namespace std;
  12.  
  13. const int MAX_N = 1e5 + 1;
  14.  
  15. struct Segment_Tree{
  16.     ll tree[4 * MAX_N + 5];
  17.  
  18.     void update(int id, int l, int r, int pos, ll val){
  19.         if(l == r){
  20.             tree[id] = min(tree[id], val);
  21.             return;
  22.         }
  23.  
  24.         int m = (l + r) / 2;
  25.         if(pos <= m) update(id * 2, l, m, pos, val);
  26.         else update(id * 2 + 1, m + 1, r, pos, val);
  27.  
  28.         tree[id] = min(tree[id * 2], tree[id * 2 + 1]);
  29.     }
  30.  
  31.     ll query(int id, int tl, int tr, int l, int r){
  32.         if(tl > tr || l > r || r < tl || tr < l) return 1e18;
  33.         if(l <= tl && tr <= r) return tree[id];
  34.  
  35.         int tm = (tl + tr) / 2;
  36.         return min(query(id * 2, tl, tm, l, r),
  37.                    query(id * 2 + 1, tm + 1, tr, l, r));
  38.     }
  39. }seg;
  40.  
  41. struct Hao{
  42.     int in, out, cost;
  43.  
  44.     bool operator <(const Hao &other){
  45.         if(in != other.in) return in < other.in;
  46.         return in < other.in; // sort theo in
  47.     }
  48. };
  49.  
  50. Hao a[MAX_N + 5];
  51. ll dp[MAX_N + 5];
  52. int n, m;
  53.  
  54. // mình không thích thời gian bắt đầu từ 0 nên mình sẽ cộng 1 ở mọi chỗ để thời gian bắt đầu từ 1(không làm cũng được)
  55. void Input(){
  56.     cin >> n >> m;
  57.     n++;
  58.  
  59.     for(int i = 1; i <= m; i++){
  60.         cin >> a[i].in >> a[i].out >> a[i].cost;
  61.         a[i].in++;
  62.         a[i].out = min(a[i].out + 1, n); // sẽ có 1 số cái lớn hơn n nên phải lấy min(a[i].out, n)
  63.     }
  64.     sort(a + 1, a + m + 1);
  65. }
  66.  
  67. void Solve(){
  68. 	// khởi tạo ban đầu mọi thứ lớn vô cùng
  69.     memset(dp, 0x3f, sizeof(dp));
  70.     memset(seg.tree, 0x3f, sizeof(seg.tree));
  71.  
  72.     //gán thời gian ban đầu 1 là 0
  73.     seg.update(1, 1, n, 1, 0);
  74.     dp[1] = 0;
  75.  
  76.     for(int i = 1; i <= m; i++){
  77.     	//tìm dp bé nhất trong đoạn a[i].in -> a[i].out
  78.     	//lấy từ a[i].in chứ không phải a[i].in - 1 là do tất cả các đoạn phải nối nhau
  79.     	// ví dụ như [3, 4] và [5, 6] thì không được nhưng [3, 4] và [4, 6] mới được
  80.         ll best = seg.query(1, 1, n, a[i].in, a[i].out);
  81.  
  82.         //tính dp
  83.         dp[a[i].out] = min(dp[a[i].out], best + a[i].cost);
  84.  
  85.         //update lại
  86.         seg.update(1, 1, n, a[i].out, dp[a[i].out]);
  87.     }
  88.  
  89. 	//cout kết quả
  90.     cout << dp[n];
  91. }
  92.  
  93. int main(){
  94.     ios_base::sync_with_stdio(0);
  95.     cin.tie(0);
  96.  
  97.     Input();
  98.     Solve();
  99. }
  100.  
Success #stdin #stdout 0.01s 8392KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/zUHpN8
language:
C++14 (gcc 8.3)
created:
1 hour ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!