0x58 数据结构优化DP

清理班次

题意：

给定区间 $[1,T]$，给定 $n$ 条线段 [li,ri][l_i, r_i][li​,ri​]，选择最少数量的线段，使区间每个点都被覆盖

解析：

将所有线段按右端点 rir_iri​ 升序排序。

令 fif_ifi​ 为覆盖区间 $[1,i]$ 所有点的最少线段数。对每条线段 [li,ri][l_i, r_i][li​,ri​]，都有转移 fri=min⁡(fri,min⁡j=li−1rifj+1)f_{r_i} = \\min(f_{r_i},\\min\\limits_{j = l_i-1}\\limits^{r_i}f_j+1)fri​​=min(fri​​,j=li​−1minri​​fj​+1)

时间复杂度为 O(n2)O(n^2)O(n2)

但可以发现 min⁡j=li−1rifj\\min\\limits_{j = l_i-1}\\limits^{r_i}f_jj=li​−1minri​​fj​ 是区间最小值，可以用线段树维护最小值，支持区间查询和单点修改。

初值 f0f_0f0​ = 0，将所有点的坐标+1。因此初值为 f1=0f_1 = 0f1​=0

代码：

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef double db;
#define fi first
#define se second
#define debug(x) cerr << #x << ": " << (x) << endl
#define rep(i, a, b) for(int i = (a); i <= (b); i++)
const int maxn = 1e6+10;
const int maxm = 1e5+10;
const int INF = 0x3f3f3f3f;
typedef pair<int, int> pii;struct seg{int l, r;seg(){}seg(int l, int r) : l(l), r(r){}bool operator < (const seg &b) const{return r < b.r;}
}s[maxn];
int f[maxn];
int n, T, l, r;inline int ls(int x){return x << 1;}
inline int rs(int x){return x << 1 | 1;}int t[maxn << 2];
void pushup(int k){t[k] = min(t[ls(k)], t[rs(k)]);
}
void build(int k, int l, int r){if(l == r){t[k] = INF;return;}int mid = (l+r) >> 1;build(ls(k), l, mid);build(rs(k), mid+1, r);pushup(k);
}
void modify(int k, int l, int r, int pos, int v){if(l == r && l == pos){t[k] = v;return;}int mid = (l+r) >> 1;if(pos <= mid)modify(ls(k), l, mid, pos, v);elsemodify(rs(k), mid+1, r, pos, v);pushup(k);
}
int query(int k, int l, int r, int x, int y){if(x <= l && y >= r)return t[k];int mid = (l+r) >> 1;int res = INF;if(x <= mid)res = min(res, query(ls(k), l, mid, x, y));if(y > mid)res = min(res, query(rs(k), mid+1, r, x, y));return res;
}int main(){ios::sync_with_stdio(false);cin.tie(0); cout.tie(0);cin >> n >> T;T++;rep(i, 1, n){cin >> l >> r;l++, r++;l = max(2, l); r = min(T, r);s[i] = seg(l, r);}sort(s+1, s+1+n);build(1, 1, T);modify(1, 1, T, 1, 0);memset(f, INF, sizeof(f));f[1] = 0;rep(i, 1, n){f[s[i].r] = min(f[s[i].r], query(1, 1, T, s[i].l-1, s[i].r)+1);modify(1, 1, T, s[i].r, f[s[i].r]);}if(f[T] == INF)cout << -1 << endl;elsecout << f[T] << endl;return 0;
}

清理班次2

题意：

给定区间 $[M,E]$，给定 $n$ 条线段 [li,ri][l_i, r_i][li​,ri​]，选择该线段的代价为 cic_ici​，询问使 $[M,E]$ 被覆盖的最小代价。

解析：

基本同上题。

fif_ifi​ 表示覆盖区间 $[M,i]$ 的最小代价。

对于每条线段，fbi=min⁡(fbi,min⁡j=li−1rifj+ci)f_{b_i} = \\min(f_{b_i},\\min\\limits_{j = l_i-1}\\limits^{r_i}f_j+c_i)fbi​​=min(fbi​​,j=li​−1minri​​fj​+ci​)

代码：

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef double db;
#define fi first
#define se second
#define debug(x) cerr << #x << ": " << (x) << endl
#define rep(i, a, b) for(int i = (a); i <= (b); i++)
const int maxn = 1e5+10;
const int maxm = 1e5+10;
const ll INF = 0x3f3f3f3f3f3f3f3f;
typedef pair<int, int> pii;struct seg{int l, r; ll c;seg(){}seg(int l, int r, ll c) : l(l), r(r), c(c){}bool operator < (const seg &b) const{return r < b.r;}
}s[maxn];
ll f[maxn];
int n, L, R, l, r, w;inline int ls(int x){return x << 1;}
inline int rs(int x){return x << 1 | 1;}ll t[maxn << 2];
void pushup(int k){t[k] = min(t[ls(k)], t[rs(k)]);
}
void build(int k, int l, int r){if(l == r){t[k] = INF;return;}int mid = (l+r) >> 1;build(ls(k), l, mid);build(rs(k), mid+1, r);pushup(k);
}
void modify(int k, int l, int r, int pos, ll v){if(l == r && l == pos){t[k] = v;return;}int mid = (l+r) >> 1;if(pos <= mid)modify(ls(k), l, mid, pos, v);elsemodify(rs(k), mid+1, r, pos, v);pushup(k);
}
ll query(int k, int l, int r, int x, int y){if(x <= l && y >= r)return t[k];int mid = (l+r) >> 1;ll res = INF;if(x <= mid)res = min(res, query(ls(k), l, mid, x, y));if(y > mid)res = min(res, query(rs(k), mid+1, r, x, y));return res;
}int main(){ios::sync_with_stdio(false);cin.tie(0); cout.tie(0);cin >> n >> L >> R;L++, R++;rep(i, 1, n){cin >> l >> r >> w;l++, r++;l = max(l, L); r = min(r, R);s[i] = seg(l, r, w);}sort(s+1, s+1+n);build(1, L-1, R);modify(1, L-1, R, L-1, 0);memset(f, INF, sizeof(f));f[L-1] = 0;rep(i, 1, n){f[s[i].r] = min(f[s[i].r], query(1, L-1, R, s[i].l-1, s[i].r) + s[i].c);modify(1, L-1, R, s[i].r, f[s[i].r]);}if(f[R] == INF)cout << -1 << endl;elsecout << f[R] << endl;return 0;
}

赤壁之战

题意：

给定长度为 $n$ 的序列 $a$，询问有多少个长度为 $m$ 的严格递增子序列。

解析：

令 fi,jf_{i,j}fi,j​ 为在以第 $i$ 个数为结尾的，长度为 $j$ 的严格递增子序列的个数

长度大的递增子序列是由长度小的递增子序列后面接上几个数形成的，所以按长度划分dp 的阶段。

fi,j=∑k=1i−1fk,j−1[ak<ai]f_{i,j} = \\sum\\limits_{k=1}\\limits^{i-1} f_{k, j-1}[a_k < a_i]fi,j​=k=1∑i−1​fk,j−1​[ak​<ai​]

时间复杂度为 O(n3)O(n^3)O(n3)，需要优化。

对于长度为 $j$ 的阶段，需要快速求和上一阶段满足条件的状态。对 $i$ 而言，上一阶段有贡献的状态需要满足条件：$k<i$ 且 ak<aia_k<a_iak​<ai​，二维偏序，可以用树状数组在 $\log n$ 的时间内解决。

所以，用树状数组维护上一阶段的状态，在本阶段，查询 ai−1a_i-1ai​−1 的前缀和。

初始条件：fi,1=1f_{i,1} = 1fi,1​=1，需要离散化，答案为 ∑i=1nfi,m\\sum\\limits_{i=1}\\limits^n f_{i, m}i=1∑n​fi,m​

代码：

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef double db;
#define fi first
#define se second
#define debug(x) cerr << #x << ": " << (x) << endl
#define rep(i, a, b) for(int i = (a); i <= (b); i++)
const int maxn = 5e3+10;
const int maxm = 5e3+10;
const ll mod = 1e9+7;
const int N = 5e3;
const int INF = 0x3f3f3f3f;
typedef pair<int, int> pii;inline int lowbit(int x){return x & (-x);}
struct BIT{ll c[maxn];void add(int x, int v){for(; x <= N; x += lowbit(x))c[x] = (c[x] + v) % mod;}ll query(int x){ll res = 0;while(x){res = (res+c[x]) % mod;x -= lowbit(x); }return res;}void init(){memset(c, 0, sizeof(c));}
}tr;
ll dp[maxn][maxn];
vector<ll> t;
ll a[maxn], n, m;
void solve(int T){cin >> n >> m;t.clear();tr.init();for(int i = 1; i <= n; i++){cin >> a[i];t.push_back(a[i]);}sort(t.begin(), t.end());t.erase(unique(t.begin(), t.end()), t.end());for(int i = 1; i <= n; i++)a[i] = lower_bound(t.begin(), t.end(), a[i])-t.begin()+1;for(int i = 1; i <= n; i++)dp[i][1] = 1;for(int len = 2; len <= m; len++){tr.init();for(int i = 1; i <= n; i++){dp[i][len] = tr.query(a[i]-1);tr.add(a[i], dp[i][len-1]);}}int res = 0;for(int i = 1; i <= n; i++)res = (res + dp[i][m]) % mod;printf("Case #%d: ", T);cout << res << endl;return;
}
int main(){int T;cin >> T;for(int i = 1; i <= T; i++){		solve(i);}return 0;
}