### 0.Update
---
2022.8.14 9:41 发表此篇博文。
2022.8.14 14:48 更改博文名为 “【杂题】思维题做题笔记”。
### 1.AT2273 [ARC066C] Addition and Subtraction Hard
原始难度：$2709$。
---
一道很有意思的基于性质的贪心题。
观察原式可以发现一点重要的性质：
- **结论一** 在 `+` 号后面加括号一定没用，因为不会变号，所以所有括号都是在 `-` 号后面。
我们再定义一个基本概念：**括号嵌套**。
有两个成对的括号 $S$ 和 $T$，记 $S$ 的左括号所在下标为 $l_0$，右括号所在下标为 $r_0$，$T$ 的左括号所在下标为 $l_1$，右括号所在下标为 $r_1$，如果出现 $l_0 \le l_1 < r_1 \le r_0$ 的情况，则 $S$ 和 $T$ **嵌套**。
根据这个性质，我们得到一条**推论**：最优方案一定不会出现两个以上的括号嵌套的情况。
**证明**：根据结论一可得，如果存在两个括号嵌套的情况，必然满足这两个括号的左端点所在下标之前必然是 `-` 号，对于形似 `-(A - (B op C))` 的情况，我们对 `op` 进行分讨：
若 `op = +`，那经过两次 `-` 的变号，`op` 仍然为 `+`，不会让答案变得更劣。
若 `op = -`，我们显然可以发现，如果没有括号嵌套， `op` 会通过一次变号变成 `+`，使得答案更优，所以不嵌套比嵌套更优。
通过这个**推论**，我们能证明一个**关键结论**：对于括号内的一个表达式 `-(A op1 B op2 C ...... )`，他的最优情况一定是形如 `-(A - (B + C + ...... + N) - O - ..... - (X + Y + ...... + Z))` 的情况（可以理解为 `+` 号放在括号内的嵌套括号中，`-` 号直接放在括号中）。这个很显然，我就不证了。
同样可以引申出另一个**推论**：最优的方案不会出现两个没有**交集**的括号。这个也很显然，将两个没有交集的括号按照关键结论中的构造方案来构造，不会使得答案更劣。
我们引入两个数组 $sum$ 和 $ans$，定义 $sum_k = \sum_{i = 1}^{k} a_i$，特别的，对于 $op_i = \texttt{"-"}$ 的情况，$a_i = -a_i$，定义 $ans_k=\sum_{i = 1}^{k} |a_i|$。
我们考虑枚举两个相邻的 $op_i = \texttt{"-"}$，相邻的定义是对于 $i,j\in[1,n] \land op_i,op_j = \texttt{"-"}$，对于 $\forall x\in(i,j)$，$op_x = \texttt{"+"}$。我们将 $i$ 钦定为 $l_0$，$j$ 钦定为 $l_1$ （参考之前的定义），此时的最优解为
$$res = sum_i - (sum_{j-1} - sum_i) + (ans_n - ans_{j-1})$$
简单解释一下，由于 $x\in(i,j)$ 的这些 $op_x = \texttt{"+"}$ 的情况，没法通过括号嵌套加上这部分的贡献（找不到第二个 `-`），只能变号，所以我们要减去这一段，而对于 $x\in[1,i]$，前面都没有括号，所以对答案没有影响，所以直接加上 $sum_i$ 即可，对于 $x\in[j,n]$，我们通过构造方案能够累加这部分的所有贡献，所以要加上 $ans_n - ans_{j - 1}$。
然后记得和 $sum_n$ 比较一下，我就被这里卡了一次，假如不存在相邻的减号或者相邻减号的答案不优就会寄。
代码：
```cpp
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
inline ll read(){
ll x = 0,f = 1;
char ch = getchar();
while(ch < '0' || ch > '9'){
if(ch == '-')
f = -1;
ch = getchar();
}
while(ch >= '0' && ch <= '9'){
x = (x << 1) + (x << 3) + (ch ^ 48);
ch = getchar();
}
return x * f;
}
ll n, a[100005], ok, sum[100005], ans[100005], dx[100005], cnt;
char s[100005][3];
int main(){
n = read();
a[1] = read();
sum[1] = ans[1] = a[1];
for(int i = 2; i <= n; ++i){
scanf("%s", s[i] + 1);
a[i] = read();
sum[i] = sum[i - 1] + (s[i][1] == '+' ? a[i] : -a[i]);
ans[i] = ans[i - 1] + a[i];
if(s[i][1] == '-') dx[++cnt] = i;
}
ll res = sum[n];
for(int i = 1; i < cnt; ++i){
res = max(res, sum[dx[i]] + ans[n] - ans[dx[i + 1] - 1] - sum[dx[i + 1] - 1] + sum[dx[i]]);
}
printf("%lld\n", res);
return 0;
}
```
### 2.CF768D Jon and Orbs
原始难度：$2200$
----
很水的一道概率 DP，不知道为啥能有*2200/yiw。
不难发现，这题的关键点在于求出第 $i$ 天选到 $j$ 个物品的概率，于是我们将这个设置为状态，即 $dp_{i,j}$ 为第 $i$ 天选到 $j$ 个物品的概率。
转移就很明了了，我们对第 $i$ 天选到的物品进行分类讨论：
定义第 $i-1$ 天选到的物品集合为 $V$，第 $i$ 天选到的物品为 $x$。
- 若 $x\in V$，选到 $x$ 的概率是在 $n$ 个物品中选 $|V|$ 个的概率，即 $\frac{|V|}{n}$，此时 $|V| = j$。
- 若 $x\not\in V$，选到 $x$ 的概率是在 $n$ 个物品中选 $n - |V|$ 个的概率，即 $\frac{n - |V|}{n}$，此时 $|V| = j - 1$。
所以这题的转移就出来了：
- 对于 $i\in(1,lim],j\in[1,n]$，$dp_{i,j} = dp_{i-1,j} \times \frac{j}{n} + dp_{i-1,j-1} \times \frac{n - j + 1}{n}$，$lim$ 是可能的答案最大值。
初始化：显然第 $1$ 天绝对能选到 $1$ 种物品，所以 $dp_{1,1}= 1$。
更新答案：从小到大枚举 $i\in[1,lim]$，若 $dp_{i,n} \ge \frac{p_j}{2000}\land dp_{i-1,n} < \frac{p_j}{2000}$，更新第 $j$ 个询问的答案为 $i$。
通过对极限数据的测试，这题的答案上界 $lim = 7274$，实测将数组大小开为 $7275 \times 1005$ 可以 AC。
代码：
```cpp
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
inline int read(){
int x = 0,f = 1;
char ch = getchar();
while(ch < '0' || ch > '9'){
if(ch == '-')
f = -1;
ch = getchar();
}
while(ch >= '0' && ch <= '9'){
x = (x << 1) + (x << 3) + (ch ^ 48);
ch = getchar();
}
return x * f;
}
int k, q, p[1005], maxn, ans[1005];
double dp[7275][1005];// 第i天，取到j种物品的概率
int main(){
k = read(), q = read();
for(int i = 1; i <= q; ++i) p[i] = read();
dp[1][1] = 1;
for(int i = 2; i <= 7274; ++i){
for(int j = 1; j <= k; ++j){
dp[i][j] += dp[i - 1][j] * (j * 1.0 / k);
dp[i][j] += dp[i - 1][j - 1] * ((k - j + 1) * 1.0 / k);
}
}
for(int i = 1; i <= 7274; ++i){
// printf("%.6lf\n", dp[i][k]);
for(int j = 1; j <= q; ++j){
if(dp[i][k] >= (p[j] * 1.0 / 2000) && !ans[j]) ans[j] = i;
}
}
for(int i = 1; i <= q; ++i) printf("%d\n", ans[i]);
return 0;
}
```
### 3.Hdu 4035 Maze
---
好玩的树形 DP。
题意：给定有 $n$ 个点的迷宫，每个点有两个概率 $k_i$，$e_i$，表示有 $k_i$ 的概率回到起点 $1$，有 $e_i$ 的概率逃出迷宫，求解逃出迷宫的期望步数。
思路：考虑 $dp$，记 $dp_i$ 为点 $i$ 逃出迷宫的期望步数。
我们对点 $i$ 进行分讨，记 $t_i = (1 - k_i - e_i)$，$f_i$ 为点 $i$ 的父亲，$son_i$ 为点 $i$ 的儿子的集合：
- 若点 $i$ 为叶子节点：$dp_i = k_i \times dp_1 + t_i \times (dp_{f_i} + 1)$
- 若点 $i$ 不为叶子节点 $dp_i = k_i \times dp_1 + \frac{t_i}{m} \times (dp_{f_i} + 1 + \sum_{j\in son_i}(dp_j + 1))$
这个时候出现了一个问题，这个转移存在**后效性**，也就是说后面转移的状态会影响前面的，这个时候我们就要考虑如何去掉后效性。
通过观察式子可以发现，导致 $dp$ 存在后效性的关键因素是 $dp_1$ 和 $dp_{f_i}$，我们考虑把这个式子转化成方程求解。
设： $dp_i = a_i\times dp_1 + b_i \times dp_{f_i} + c_i $。
我们对原来的转移进行化简：
- 对于点 $i$ 为叶子节点的情况，易得 $dp_i = k_i \times dp_1 + t_i \times dp_{f_i} + t_i$，所以 $a_i = k_i$，$b_i = t_i$，$c_i = t_i$。
- 对于点 $i$ 不为叶子节点的情况：
$$\begin{aligned}
dp_i&=k_i \times dp_1 + \frac{t_i}{m} \times (dp_{f_i} + \sum_{j\in son_i}(dp_j + 1))\\
&=k_i \times dp_1 + \frac{t_i}{m} \times dp_{f_i} + \frac{t_i}{m} \times \sum_{j\in son_i}dp_j + t_i\\
\end{aligned}$$
我们考虑将 $\sum_{j\in son_i}dp_j$ 进行转化，即 $\sum_{j\in son_i}dp_j = dp_1 \times \sum a_j + dp_{i} \times \sum b_j + \sum c_j$，带入原式得：
$$\begin{aligned}
dp_i &= k_i \times dp_1 + \frac{t_i}{m} \times dp_{f_i}+\frac{t_i}{m} \times dp_1 \times \sum a_j + dp_{i} \times \frac{t_i}{m} \times \sum b_j + \frac{t_i}{m} \times \sum c_j + t_i\\
dp_i&=(k_i + \frac{t_i}{m}\times\sum a_j) \times dp_1 + \frac{t_i}{m} \times dp_{f_i} + \frac{t_i}{m} \times \sum b_j \times dp_i + \frac{t_i}{m} \times \sum c_j + t_i\\
{(1-\frac{t_i}{m} \times \sum b_j)}\times dp_i&=(k_i + \frac{t_i}{m}\times\sum a_j) \times dp_1 + \frac{t_i}{m} \times dp_{f_i} + \frac{t_i}{m} \times \sum c_j + t_i\\
dp_i &= \frac{(k_i + \frac{t_i}{m}\times\sum a_j)}{(1-\frac{t_i}{m} \times \sum b_j)} \times dp_1 + \frac{\frac{t_i}{m} }{(1-\frac{t_i}{m} \times \sum b_j)}\times dp_{f_i} + \frac{\frac{t_i}{m} \times \sum c_j + t_i}{(1-\frac{t_i}{m} \times \sum b_j)}
\end{aligned}$$
这时可得 :
$$a_i = \frac{(k_i + \frac{t_i}{m}\times\sum a_j)}{(1-\frac{t_i}{m} \times \sum b_j)}$$
$$b_i = \frac{\frac{t_i}{m} }{(1-\frac{t_i}{m} \times \sum b_j)}$$
$$c_i = \frac{\frac{t_i}{m} \times \sum c_j + t_i}{(1-\frac{t_i}{m} \times \sum b_j)}$$
这时只需自下向上更新 $a_i$，$b_i$，$c_i$ 的值即可。
对于答案，$dp_1 = a_1\times dp_1 + c_1$。
这时可以化简为 $dp_1 = \frac{c_1}{1 - a_1}$，输出即可。
注意判断无解情况：若 ${(1-\frac{t_i}{m} \times \sum b_j)}=0 \lor 1 - a_1 = 0$，则无解。
代码：
```cpp
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
inline int read(){
int x = 0,f = 1;
char ch = getchar();
while(ch < '0' || ch > '9'){
if(ch == '-')
f = -1;
ch = getchar();
}
while(ch >= '0' && ch <= '9'){
x = (x << 1) + (x << 3) + (ch ^ 48);
ch = getchar();
}
return x * f;
}
int T, n, x, y, ok, tmp;
double k[10005], e[10005], a[10005], b[10005], c[10005], t[10005];
const double eps = 1e-10;
vector<int> d[10005];
bool dp(int x, int fa){
if(d[x].size() == 1 && x != 1){
a[x] = k[x];
b[x] = c[x] = t[x];
return 1;
}
double s1 = 0, s2 = 0, s3 = 0;
for(int i = 0; i < d[x].size(); ++i){
int y = d[x][i];
if(y == fa) continue;
if(dp(y, x) == 0) return 0;
s1 += a[y];
s2 += b[y];
s3 += c[y];
}
double m = (double)d[x].size();
if((1 - t[x] / m * s2) <= eps){
return 0;
}
a[x] = (k[x] + t[x] / m * s1) / (1 - t[x] / m * s2);
b[x] = (t[x] / m) / (1 - t[x] / m * s2);
c[x] = (t[x] / m * s3 + t[x]) / (1 - t[x] / m * s2);
return 1;
}
int main(){
T = read();
while(T--){
for(int i = 1; i <= n; ++i) a[i] = b[i] = c[i] = 0.00, d[i].clear();
n = read();
for(int i = 1; i < n; ++i){
x = read(), y = read();
d[x].push_back(y);
d[y].push_back(x);
}
for(int i = 1; i <= n; ++i){
scanf("%lf%lf", &k[i], &e[i]);
k[i] /= 100;
e[i] /= 100;
t[i] = (double)1 - k[i] - e[i];
}
if(!dp(1, 0) || (1 - a[1]) <= eps) printf("Case %d: impossible\n", ++tmp);
else printf("Case %d: %.6lf\n", ++tmp, c[1] / (1 - a[1]));
}
return 0;
}
```
### 4.JZOJ4210 | ZROJ458 我才不是萝莉控呢
---
神仙的转化题。
题意：你被困在一个 $n\times n$ 的网格中，且你有一个长为 $n$ 的序列 $a$，这个网格的起点是 $(n,1)$ ，终点是 $(1,1)$，在不走出网格的前提下，你有两种行动方式：
- 从 $(i,j)$ 走到 $(i-1,j+1)$，花费为 $0$。
- 从 $(i,j)$ 走到 $(i,\lceil\frac{j}{2}\rceil)$，花费为 $\sum_{k=i}^{n} a_k$。
求走到终点的最小花费。
思路：首先考虑 $dp$，记 $dp_{i,j}$ 为走到点 $(i,j)$ 的最小花费，有如下转移：
$dp_{i,j} = \min(dp_{i+1,j-1},dp_{i,j\times2} +\sum_{k=i}^{n}a_k)$。
但是很明显这时转移的时间复杂度是 $\mathrm{O}(n^2)$，不能够通过 $n = 10^5$ 量级的数据，这时考虑对 $dp$ 进行优化。
这里的优化很神仙，我们观察这个转移方程，通过思考，可以与一个数据结构联系起来：**哈夫曼树**。
如果我们将 $dp$ 的二维状态看成一棵树上拥有前 $i$ 个带权叶子节点和 $j$ 个空叶子节点的树权，这时的 $dp_{i,j} = dp_{i+1,j-1}$ 就是将 $j$ 个空叶子节点中的其中一个赋值为 $a_{i+1}$，这时 $dp_{i,j} = dp_{i,j\times2}+\sum_{k=i}^{n} a_k$
可以看作对于每个深度为 $dep_j$ 的空叶子节点，将它分裂成两个深度为 $dep_j + 1$ 的空叶子节点，这时如果插入 $a$ 中剩下的 $n - i + 1$ 个数，总共会增加
$$\begin{aligned}
(dep_j + 1)\times\sum_{k=i}^{n} a_k - dep_j \times \sum_{k=i}^{n} a_k = \sum_{k=i}^{n} a_k
\end{aligned}$$
的树权，这其实也很像**费用提前计算**的思想。
对于所有可能的树的形态，我们要求出树权最小的一个，显然这时哈夫曼树就满足这个条件，于是我们通过广为人知的方式构造出哈夫曼树即可，时间复杂度优化到 $\mathrm{O}(n \log n)$。
代码：
```cpp
#include<bits/stdc++.h>
using namespace std;
#define int long long
typedef long long ll;
inline int read(){
int x = 0,f = 1;
char ch = getchar();
while(ch < '0' || ch > '9'){
if(ch == '-')
f = -1;
ch = getchar();
}
while(ch >= '0' && ch <= '9'){
x = (x << 1) + (x << 3) + (ch ^ 48);
ch = getchar();
}
return x * f;
}
int T, n, a[100005], ans;
priority_queue<int, vector<int>, greater<int> > q;
signed main(){
T = read();
while(T--){
ans = 0;
n = read();
for(int i = 1; i <= n; ++i) a[i] = read(), q.push(a[i]);
while(q.size() > 1){
int x = q.top(); q.pop();
int y = q.top(); q.pop();
ans += x + y;
q.push(x + y);
}
while(q.size()) q.pop();
printf("%lld\n", ans);
}
return 0;
}
```
### 5.CF1264E Beautiful League
原始难度：$2700$
---
比较巧妙的费用流题目。
考虑如何计算美丽的三元组，即三元环的个数，首先对于一个 $n$ 个点的完全图，其三元组个数显然为 $\binom{n}{3}$，即 $\frac{n\times(n - 1)\times(n - 2)}{6}$。我们想到三元环的个数可以表示为：三元组的个数 - 不是三元环的个数，我们思考不是三元环的个数，考虑如果一个三元组不是三元环，当且仅当某个点的出度为 $2$，所以我们枚举每个点出度为 $2$ 时的三元环个数，易得个数为 $\sum _{i=1}^{n}\binom{out_i}{2}$，$out_i$ 为 $i$ 的出度。所以三元环的个数就为 $\frac{n\times(n - 1)\times(n - 2)}{6} - \sum _{i=1}^{n}\binom{out_i}{2}$，我们考虑化简这个式子：
$$\begin{aligned}
\frac{n\times(n - 1)\times(n - 2)}{6} - \sum _{i=1}^{n}\binom{out_i}{2}&=\frac{n\times(n - 1)\times(n - 2)}{6} - \sum _{i=1}^{n}\frac{out_i\times(out_i - 1)}{2}\\
&=\frac{n\times(n - 1)\times(n - 2)}{6} - \sum _{i=1}^{n}\frac{out_i^2-out_i}{2}
\end{aligned}$$
不难发现 $\sum_{i=1}^{n} out_i=\frac{(n)\times(n-1)}{2}$，所以我们要解决的是最小化 $\sum_{i=1}^{n} out_i^2$，这时考虑怎么建模，对于图上的边，有一个比较套路的建模方式，将每条边看做一个点与源点连接，流量为 $1$，费用为 $0$，将这个点与这条边左右端点分别连接，流量为 $1$，费用为 $0$，对于每个点连 $x$ 条向汇点的边，$x=n-d_i$，$d_i$ 代表点 $i$ 在已经固定的边的出度，考虑到令 $out_i \gets out_{i}+1$ 对答案的影响，因为 $(out_i + 1) ^ 2-out_i^2 = 2\times out_i + 1$，我们将满足 $1\le k \le x$ 的第 $k$ 边的流量设为 $1$，费用为 $2\times (k+d_i) + 1$ 即可。
之后就是套板子了，我采用了 Primal_Dual 原始对偶算法来求解本题。
代码：
```cpp
#include<bits/stdc++.h>
using namespace std;
#define int long long
typedef long long ll;
inline int read(){
int x = 0,f = 1;
char ch = getchar();
while(ch < '0' || ch > '9'){
if(ch == '-')
f = -1;
ch = getchar();
}
while(ch >= '0' && ch <= '9'){
x = (x << 1) + (x << 3) + (ch ^ 48);
ch = getchar();
}
return x * f;
}
int n, m, u, v, mp[55][55], cnt = 1, s, t, in[55], nxt[3005], h[3005], fn[3005], vis[3005], dis[3005];
pair<int, int> bs[3005];
struct edge{
int u, v, lst, w, c;
}d[100005];
void SPFA(){
memset(h, 63, sizeof(h));
h[s] = 0;
queue<int> q;
q.push(s), vis[s] = 1;
while(q.size()){
int x = q.front(); q.pop(); vis[x] = 0;
for(int i = nxt[x]; i; i = d[i].lst){
int y = d[i].v, val = d[i].w, cost = d[i].c;
if(val && h[y] > h[x] + cost){
h[y] = h[x] + cost;
if(!vis[y]){
q.push(y);
vis[y] = 1;
}
}
}
}
}
bool Dijkstra(){
memset(dis, 63, sizeof(dis));
memset(vis, 0, sizeof(vis));
dis[s] = 0;
priority_queue< pair<int, int>, vector< pair<int, int> >, greater< pair<int, int> > > q;
q.push(make_pair(0, s));
while(q.size()){
int x = q.top().second; q.pop();
if(vis[x]) continue;
vis[x] = 1;
for(int i = nxt[x]; i; i = d[i].lst){
int y = d[i].v, val = d[i].w, cost = d[i].c + h[x] - h[y];
if(val && dis[x] + cost < dis[y]){
dis[y] = dis[x] + cost;
fn[y] = i;
q.push(make_pair(dis[y], y));
}
}
}
// for(int i = 1; i <= n * n + n + 1; ++i){
// printf("%lld kk\n", dis[i]);
// }
return (dis[t] != dis[t + 1]);
}
void Primal_Dual(){
SPFA();
int sum = 0, tot = 0;
while(Dijkstra()){
// printf("orz zxx\n");
int minf = 1e18;
for(int i = 1; i <= n; ++i) h[i] += dis[i];
for(int i = t; i != s; i = d[fn[i]].u){
minf = min(minf, d[fn[i]].w);
}
for(int i = t; i != s; i = d[fn[i]].u){
d[fn[i]].w -= minf;
d[fn[i] ^ 1].w += minf;
}
sum += minf;
tot += minf * dis[t];
}
for(int i = 1; i <= n; ++i){
for(int j = 1; j <= n; ++j){
if(!d[bs[i * n + j].first].w) mp[d[bs[i * n + j].first].v][d[bs[i * n + j].second].v] = 1;
else if(!d[bs[i * n + j].second].w) mp[d[bs[i * n + j].second].v][d[bs[i * n + j].first].v] = 1;
}
}
for(int i = 1; i <= n; ++i){
for(int j = 1; j <= n; ++j) printf("%d", mp[i][j]);
putchar('\n');
}
}
void add(int a, int b, int c, int cost){
d[++cnt].u = a, d[cnt].v = b, d[cnt].w = c, d[cnt].c = cost;
d[cnt].lst = nxt[a], nxt[a] = cnt;
}
signed main(){
n = read(), m = read();
for(int i = 1; i <= m; ++i){
u = read(), v = read();
mp[u][v] = 1;
in[u]++;
}
s = 0, t = n * n + n + 1;
for(int i = 1; i <= n; ++i){
for(int j = i + 1; j <= n; ++j){
if(mp[i][j] | mp[j][i]) continue;
add(0, i * n + j, 1, 0);
add(i * n + j, 0, 0, 0);
add(i * n + j, i, 1, 0);
bs[i * n + j].first = cnt;
add(i, i * n + j, 0, 0);
add(i * n + j, j, 1, 0);
bs[i * n + j].second = cnt;
add(j, i * n + j, 0, 0);
}
}
for(int i = 1; i <= n; ++i){
for(int j = 1; j <= n - in[i]; ++j){
add(i, t, 1, 2 * (j + in[i]) + 1);
add(t, i, 0, -(2 * (j + in[i]) + 1));
}
}
Primal_Dual();
return 0;
}
```
### 6.P4310 绝世好题
---
一道基础的线性 dp 练习题。
这题的转移很经典，定义 $dp_i$ 为 $1$ 到 $i$ 的最优答案。
显然有如下转移：$dp_i = \max(dp_i, dp_j + 1)$，其中 $j\in[1,i) \land a_i \& a_j \neq 0$，在以下答案取最优值即可。
但是朴素转移，时间复杂度是 $\mathrm{O}(n^2)$ 的，很劣，而这题的难点就在于如何优化转移。
考虑按位与的性质，观察转移方程可以看出，由于我们只关心最大值，所以切入点就在于在满足限制条件的前提下快速找到最大值，这个时候我们有一个比较常见的 trick，就是**按位分组**。定义 $t_i$ 为二进制分解下第 $i$ 为 $1$ 当前的最优值，假设现在我们求解下标为 $j$ 的情况，可以对 $a_j$ 进行二进制拆分，如果 $a_j$ 的第 $k$ 为 $1$，就将 $dp_j$ 和 $t_k + 1$ 取最大值，同理在求出最终的 $dp_j$ 时，也要用 $dp_j$ 去更新 $t_k$。
然后这题就做完了，时间复杂度被我们优化到了 $\mathrm{O}(n\log w)$，$w$ 为 $\max(a_i)(i\in[1,n])$。
代码：
```cpp
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
inline int read(){
int x = 0,f = 1;
char ch = getchar();
while(ch < '0' || ch > '9'){
if(ch == '-')
f = -1;
ch = getchar();
}
while(ch >= '0' && ch <= '9'){
x = (x << 1) + (x << 3) + (ch ^ 48);
ch = getchar();
}
return x * f;
}
int n, a[100005], t[35], len[35], dp[100005], er[35], cnt, ans;
int main(){
n = read();
for(int i = 1; i <= n; ++i) a[i] = read();
for(int i = 1; i <= n; ++i){
int p = a[i]; cnt = 0;
while(p){
er[++cnt] = (p & 1);
p >>= 1;
}
for(int j = 1; j <= cnt; ++j){
if(!er[j]) continue;
dp[i] = max(dp[i], t[j] + 1);
}
ans = max(ans, dp[i]);
for(int j = 1; j <= cnt; ++j){
if(er[j]) t[j] = max(t[j], dp[i]);
}
}
printf("%d\n", ans);
return 0;
}
```
标签：ch,frac,int,sum,笔记,times,做题,杂题,dp From： https://www.cnblogs.com/mirrork/p/16901779.html