T1：队长快跑
一个线性序列有两个关键字A，B，求其最长子序列满足对于任意两个位置满足若 i < j,则Ai > Bj
对于元素均匀变化的问题考虑递推，也就是元素变化的时刻对于整体所造成的影响
考虑数学归纳，若已知序列1 ~ i-1的结果，考虑当元素在i-1时刻转向i时刻所造成的影响
容易发现，当元素A(i)插入后，其影响为以元素B(i)为最小值的序列长度为之前所有元素中
值大于B(i)的元素构成的合法序列的长度 + 1;
这启发我们需要建立二维递推，也就是记录序列i，以及以A(i)为最小值的合法序列的最大长度进行转移
定义出递推维度后再次考虑转移发现，当元素A(i)插入后，除造成上述影响外，还会使得序列1 ~ i-1中
所有结尾元素大于A(i)的序列长度 + 1;
正常转移为O(n^3),但是很容易发现上述转移过程存在整体性，这启发我们可以通过数据结构进行维护
在转移时进行整体转移，很显然用权值线段树进行维护即可
代码如下：
1 #include <bits/stdc++.h>
2 using namespace std;
3 #define I int
4 #define V void
5 #define lid id << 1
6 #define rid id << 1 | 1
7 const I MAXN = 1e5 + 5;
8 I n,tmp,A[MAXN],B[MAXN],cnt,num,L[MAXN << 1];
9 inline V LSH () {
10 sort (L + 1,L + num + 1);
11 cnt = unique (L + 1,L + num + 1) - L - 1;
12 for (I i(1);i <= n; ++ i) {
13 A[i] = lower_bound (L + 1,L + cnt + 1,A[i]) - L;
14 B[i] = lower_bound (L + 1,L + cnt + 1,B[i]) - L;
15 }
16 }
17 namespace WST {
18 I maxn[MAXN << 3],lazy[MAXN << 3];
19 inline V pushdown (I id) {
20 if (!lazy[id]) return ;
21 maxn[lid] += lazy[id],maxn[rid] += lazy[id];
22 lazy[lid] += lazy[id],lazy[rid] += lazy[id];
23 lazy[id] = 0;
24 }
25 inline V update (I id) {
26 maxn[id] = max (maxn[lid],maxn[rid]);
27 }
28 V found (I id,I l,I r) {
29 if (l == r) {
30 maxn[id] = 0;
31 return ;
32 }
33 I mid (l + r >> 1);
34 found (lid,l,mid),found (rid,mid + 1,r);
35 }
36 V poi_mod (I id,I l,I r,I pos,I w) {
37 if (l == r) {
38 maxn[id] = max (maxn[id],w);
39 return ;
40 }
41 pushdown (id);
42 I mid (l + r >> 1);
43 pos <= mid ? poi_mod (lid,l,mid,pos,w) : poi_mod (rid,mid + 1,r,pos,w);
44 update (id);
45 }
46 V sec_mod (I id,I l,I r,I ql,I qr) {
47 if (ql <= l && r <= qr) {
48 maxn[id] ++ ;
49 lazy[id] ++ ;
50 return ;
51 }
52 pushdown (id);
53 I mid (l + r >> 1);
54 if (ql <= mid) sec_mod (lid,l,mid,ql,qr);
55 if (qr > mid) sec_mod (rid,mid + 1,r,ql,qr);
56 update (id);
57 }
58 I sec_que (I id,I l,I r,I ql,I qr) {
59 if (ql <= l && r <= qr) return maxn[id];
60 pushdown (id);
61 I mid (l + r >> 1),res (0);
62 if (ql <= mid) res = max (res,sec_que (lid,l,mid,ql,qr));
63 if (qr > mid) res = max (res,sec_que (rid,mid + 1,r,ql,qr));
64 return res;
65 }
66 }
67 signed main () {
68 cin >> n;
69 for (I i (1);i <= n; ++ i) {
70 cin >> A[i] >> B[i];
71 L[++num] = A[i],L[++num] = B[i];
72 }
73 LSH ();
74 WST :: found (1,1,cnt);
75 for (I i(1);i <= n; ++ i) {
76 if (A[i] <= B[i]) {
77 tmp = WST :: sec_que (1,1,cnt,B[i] + 1,cnt) + 1;
78 WST :: poi_mod (1,1,cnt,A[i],tmp);
79 }
80 else {
81 WST :: sec_mod (1,1,cnt,B[i] + 1,A[i]);
82 tmp = WST :: sec_que (1,1,cnt,A[i] + 1,cnt) + 1;
83 WST :: poi_mod (1,1,cnt,A[i],tmp);
84 }
85 }
86 cout << WST :: maxn[1];
87 }
View Code
T3：抛硬币
同样线性序列，元素均匀变化，考虑递推，发现插入新元素后，新的长度为L的子序列数由两部分组成：
首先继承序列i-1中长度为L的子序列数，其次则是新元素所构成的长度为L的子序列
同样发现递推维度应拓展到二维，记录信息，但是转移时存在的问题为新元素构成的序列可能
与i-1序列中部分序列重复，也就是考虑如何去重，发现问题本质在于寻找重复序列个数，
考虑造成重复的原因，即新元素已经出现过并构成序列，那么发现重复序列数量即为插入的新元素在上一次出现时
所构成的序列数，因此只要预处理每个元素上一次出现的位置，在转移时去重即可
另状态转移方程的原理与组合数递推原理相似，即对于每个元素只有选与不选两种可能，唯一不同就是
此问题中各个元素并不完全独立，因此需要去重
代码如下：
1 #include <bits/stdc++.h>
2 using namespace std;
3 #define I int
4 #define LL long long
5 const I MAXN = 3e3 + 5;
6 const I mod = 998244353;
7 I L,len,pos[26],last[MAXN];
8 LL f[MAXN][MAXN];
9 char init[MAXN];
10 signed main () {
11 cin >> init + 1 >> L;
12 len = strlen (init + 1);
13 for (I i(len); i ; -- i) {
14 f[i][0] = 1;
15 if (pos[init[i] - 'a']) last[pos[init[i] - 'a']] = i;
16 pos[init[i] - 'a'] = i;
17 }
18 f[0][0] = 1;
19 for (I j(1);j <= L; ++ j)
20 for (I i(1);i <= len; ++ i)
21 f[i][j] = (last[i] ? f[i - 1][j] + f[i - 1][j - 1] - f[last[i] - 1][j - 1] : f[i - 1][j] + f[i - 1][j - 1]) % mod;
22 cout << (f[len][L] + mod) % mod;
23 }
View Code
1：发现对于元素均匀变化的问题应考虑元素变化时刻对于整体所造成的影响，通常DP解决
2：DP维度的拓展在于转移的需要，也就是转移过程中需要用到的信息的记录