Acwing 362.区间(差分约束)

简介: 笔记

Acwing 362.区间


题意


41.png


数据范围

42.png


思路

43.png


代码

// Author:zzqwtcc
// Problem: 区间
// Contest: AcWing
// Time:2021-10-28 22:50:45
// URL: https://www.acwing.com/problem/content/364/
// Memory Limit: 64 MB
// Time Limit: 1000 ms
#include<bits/stdc++.h>
#include<unordered_map>
// #define int long long
#define INF 0x3f3f3f3f
#define INFL 0x3f3f3f3f3f3f3f3f
#define mod 1000000007
#define MOD 998244353
#define rep(i, st, ed) for (int (i) = (st); (i) <= (ed);++(i))
#define pre(i, ed, st) for (int (i) = (ed); (i) >= (st);--(i))
// #define debug(x,y) cerr << (x) << " == " << (y) << endl;
#define endl '\n'
using namespace std;
typedef long long LL;
typedef unsigned long long ULL;
typedef pair<int, int> PII;
template<typename T> inline T gcd(T a, T b) { return b ? gcd(b, a % b) : a; }
template<typename T> inline T lowbit(T x) { return x & -x; }
template<typename S,typename T>void debug(S s, T t){cerr << s << " == " << t << endl;}
template<typename T>void debug(T t){cerr << t << endl;}
template<typename T>void debug(T t[],int st,int ed){for(int i = st; i <=ed;++i){cerr << t[i] << " ";}cerr << endl;}
template<typename T>void debug(const vector<T>&t){for(int i =0 ; i < t.size();++i)cerr << t[i] << " ";cerr << endl;}
// template<typename T> T qmi(T a, T b = mod - 2, T p = mod) { T res = 1; b %= (p - 1 == 0 ? p : p - 1); while (b) { if (b & 1) { res = (LL)res * a % p; }b >>= 1; a = (LL)a * a % p; }return res % mod; }
const int N = 5e4 + 10, M = 4 * N;
int h[N],e[M],ne[M],w[M],idx;
int d[N], cnt[N];
bool st[N];
int n;
void add(int a,int b, int c){
  e[idx] = b,w[idx] = c,ne[idx] = h[a],h[a] = idx++;
}
bool spfa(){
  memset(d,-0x3f,sizeof d);
  stack<int>q;
  d[0] = 0;
  q.push(0);
  while(q.size()){
    int u = q.top();
    q.pop();
    st[u] = false;
    for(int i =h[u];~i;i = ne[i]){
      int j = e[i];
      int dis = w[i];
      if(d[j] < d[u] + dis){
        d[j] = d[u] + dis;
        cnt[j] = cnt[u] + 1;
        if(cnt[j] >= 50001)return false;
        if(!st[j]){
          st[j] = true;
          q.push(j);
        }
      }
    }
  }
  return true;
}
void solve() {
    cin >> n;
    memset(h,-1,sizeof h);
    while(n--){
      int a,b,c;scanf("%d%d%d",&a,&b,&c);
      add(a,b + 1,c);                                                                                                                                                                                            
    }
    for(int i = 1;i <= 50001;++i){
      add(0,i,0);
    }
    for(int i = 1; i <= 50001;++i){
      add(i - 1,i,0);
    }
    for(int i = 1; i <= 50001;++i){
      add(i,i - 1,-1);
    }
    spfa();
    cout << d[50001] << endl;
}
signed main() {
    //int _; cin >> _;
    //while (_--)
        solve();
    return 0;
}



目录
相关文章
|
4月前
【每日一题Day302】LC849到最近的人的最大距离 | 贪心+分类讨论
【每日一题Day302】LC849到最近的人的最大距离 | 贪心+分类讨论
26 0
|
4月前
【每日一题Day122】LC1237找出给定方程的正整数解 | 双指针 二分查找
【每日一题Day122】LC1237找出给定方程的正整数解 | 双指针 二分查找
22 0
|
7月前
|
索引
每日一题 Leetcode-1499满足不等式的最大值
每日一题 Leetcode-1499满足不等式的最大值
38 0
|
9月前
|
人工智能
线性DP——AcWing 898. 数字三角形、AcWing 895. 最长上升子序列
线性DP——AcWing 898. 数字三角形、AcWing 895. 最长上升子序列
54 0
|
11月前
51nod 1711 平均数(二分 + 树状数组好题)
51nod 1711 平均数(二分 + 树状数组好题)
75 0
|
算法
LeetCode 周赛 340,质数 / 前缀和 / 极大化最小值 / 最短路 / 平衡二叉树
今天讲 LeetCode 单周赛第 340 场,今天状态不好,掉了一波大分。
57 0
AcWing 659. 区间
AcWing 659. 区间
56 0
AcWing 659. 区间