CFR 101 B. Buses ( DP + Segment Tree )
Problem - 101B - Codeforces
dp[ i ][ t[ i ] ] = sum{ dp[ i - 1 ][ s[ i ] .. t[ i ] - 1 ] }, Ɐ i: current bus
bus需要先依據終點 t做昇序排序。
注意因為區間範圍可能很大,所以需要離散化。
#include <bits/stdc++.h> using namespace std; const int MAXN = 1e9 + 9; const int MAXM = 1e5 + 5; const int MOD = 1e9 + 7; void addmod(int &x, int v){ x += v; x %= MOD; } struct itvt{ int sum; int lb, rb; itvt *lc, *rc; itvt(int _l = -1, int _r = -1): sum(0), lb(_l), rb(_r), lc(NULL), rc(NULL){} void pull(){ sum = 0; if( lc ) addmod( sum, lc->sum ); if( rc ) addmod( sum, rc->sum ); } void update(int k, int v){ if( lb == rb ){ addmod( sum, v ); return; } int mid = lb + rb >> 1; if( k <= mid ){ if( !lc ) lc = new itvt( lb, mid ); lc->update( k, v ); } else{ if( !rc ) rc = new itvt( mid + 1, rb ); rc->update( k, v ); } pull(); } int qsum(int ql, int qr){ if( qr < lb || rb < ql ) return 0; if( ql <= lb && rb <= qr ) return sum; int res = 0; if( lc ) addmod( res, lc->qsum( ql, qr ) ); if( rc ) addmod( res, rc->qsum( ql, qr ) ); return res; } }; int n, m; struct Bus{ int s, t; Bus(int _s = -1, int _t = -1): s(_s), t(_t){} bool operator < (const Bus &oth) const{ return t < oth.t; } } bus[ MAXM ]; void solve(){ itvt *root = new itvt( 0, n ); root->update( 0, 1 ); sort( bus, bus + m ); for(int i = 0; i < m; ++i) root->update( bus[ i ].t, root->qsum( bus[ i ].s, bus[ i ].t - 1 ) ); printf("%d\n", root->qsum( n, n )); } int main(){ scanf("%d%d", &n, &m); for(int i = 0; i < m; ++i) scanf("%d%d", &bus[ i ].s, &bus[ i ].t); solve(); return 0; }