### 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;
}

“`

原文地址:http://www.cnblogs.com/mirrork/p/16901779.html

1. 本站所有资源来源于用户上传和网络,如有侵权请邮件联系站长! 2. 分享目的仅供大家学习和交流,请务用于商业用途! 3. 如果你也有好源码或者教程,可以到用户中心发布,分享有积分奖励和额外收入! 4. 本站提供的源码、模板、插件等等其他资源,都不包含技术服务请大家谅解! 5. 如有链接无法下载、失效或广告,请联系管理员处理! 6. 本站资源售价只是赞助,收取费用仅维持本站的日常运营所需! 7. 如遇到加密压缩包,默认解压密码为"gltf",如遇到无法解压的请联系管理员! 8. 因为资源和程序源码均为可复制品,所以不支持任何理由的退款兑现,请斟酌后支付下载 声明:如果标题没有注明"已测试"或者"测试可用"等字样的资源源码均未经过站长测试.特别注意没有标注的源码不保证任何可用性