1. 数组推导

$A_1,A_2,\cdots ,A_n$ 是一个由 $n$ 个自然数（即非负整数）组成的数组。

在此基础上，我们用数组 $B_1\cdots B_n$ 表示 $A$ 的前缀最大值。

B i = max ⁡ { A 1 , A 2 , ⋯ , A i } B_i = \max \{ A_1, A_2, \cdots, A_i \} Bi​=max{A1​,A2​,⋯,Ai​}

如上所示，$B_i$ 定义为数组 $A$ 中前 $i$ 个数的最大值。

根据该定义易知 $A_1=B_1$，且随着 $i$ 的增大，$B_i$ 单调不降。

此外，我们用 $sum=A_1+A_2+\cdots +A_n$ 表示数组 $A$ 中 $n$ 个数的总和。

现已知数组 $B$，我们想要根据 $B$ 的值来反推数组 $A$。

显然，对于给定的 $B$，$A$ 的取值可能并不唯一。

试计算，在数组 $A$ 所有可能的取值情况中，$sum$ 的最大值和最小值分别是多少？

输入格式

输入的第一行包含一个正整数 $n$。

输入的第二行包含 $n$ 个用空格分隔的自然数 $B_1,B_2,\cdots ,B_n$。

输出格式

输出共两行。

第一行输出一个整数，表示 $sum$ 的最大值。

第二行输出一个整数，表示 $sum$ 的最小值。

数据范围

$50\%$ 的测试数据满足数组 $B$ 单调递增，即 $0<B_1<B_2<\cdots <B_n<10^5$；
全部的测试数据满足 $n\le 100$ 且数组 $B$ 单调不降，即 $0\le B_1\le B_2\le \cdots \le B_n\le 10^5$。

输入样例1：

6
0 0 5 5 10 10

输出样例1：

30
15

样例1解释

数组 $A$ 的可能取值包括但不限于以下三种情况。

• 情况一：$A=[0,0,5,5,10,10]$
• 情况二：$A=[0,0,5,3,10,4]$
• 情况三：$A=[0,0,5,0,10,0]$

其中第一种情况 $sum=30$ 为最大值，第三种情况 $sum=15$ 为最小值。

输入样例2：

7
10 20 30 40 50 60 75

输出样例2：

285
285

样例2解释

$A=[10,20,30,40,50,60,75]$ 是唯一可能的取值，所以 $sum$ 的最大、最小值均为 $285$。

变则取（a[i-1]<a[i] ，ans+=a[i]），不变 min 取0 ， max也取(ans+=a[i])

2.非零段划分

$A_1,A_2,\cdots ,A_n$ 是一个由 $n$ 个自然数（非负整数）组成的数组。

我们称其中 $A_i,\cdots ,A_j$ 是一个非零段，当且仅当以下条件同时满足：

• $1\le i\le j\le n$；
• 对于任意的整数 $k$，若 $i\le k\le j$，则 $A_k>0$；
• $i=1$ 或 $A_{i-1}=0$；
• $j=n$ 或 $A_{j+1}=0$。

下面展示了几个简单的例子：

• $A=[3,1,2,0,0,2,0,4,5,0,2]$ 中的 $4$ 个非零段依次为 $[3,1,2]$、$[2]$、$[4,5]$ 和 $[2]$；
• $A=[2,3,1,4,5]$ 仅有 $1$ 个非零段；
• $A=[0,0,0]$ 则不含非零段（即非零段个数为 $0$）。

现在我们可以对数组 $A$ 进行如下操作：任选一个正整数 $p$，然后将 $A$ 中所有小于 $p$ 的数都变为 $0$。

试选取一个合适的 $p$，使得数组 $A$ 中的非零段个数达到最大。

若输入的 $A$ 所含非零段数已达最大值，可取 $p=1$，即不对 $A$ 做任何修改。

输入格式

输入的第一行包含一个正整数 $n$。

输入的第二行包含 $n$ 个用空格分隔的自然数 $A_1,A_2,\cdots ,A_n$。

输出格式

仅输出一个整数，表示对数组 $A$ 进行操作后，其非零段个数能达到的最大值。

数据范围

$70\%$ 的测试数据满足 $n\le 1000$；
全部的测试数据满足 $n\le 5\times 10^5$，且数组 $A$ 中的每一个数均不超过 $10^4$。

输入样例1：

11
3 1 2 0 0 2 0 4 5 0 2

输出样例1：

5

样例1解释

$p=2$ 时，$A=[3,0,2,0,0,2,0,4,5,0,2]$，$5$ 个非零段依次为 $[3]$、$[2]$、$[2]$、$[4,5]$ 和 $[2]$；此时非零段个数达到最大。

输入样例2：

14
5 1 20 10 10 10 10 15 10 20 1 5 10 15

输出样例2：

4

样例2解释

$p=12$ 时，$A=[0,0,20,0,0,0,0,15,0,20,0,0,0,15]$，$4$ 个非零段依次为 $[20]$、$[15]$、$[20]$ 和 $[15]$；此时非零段个数达到最大。

输入样例3：

3
1 0 0

输出样例3：

1

样例3解释

$p=1$ 时，$A=[1,0,0]$，此时仅有 $1$ 个非零段 $[1]$，非零段个数达到最大。

输入样例4：

3
0 0 0

输出样例4：

0

样例4解释

无论 $p$ 取何值，$A$ 都不含有非零段，故非零段个数至多为 $0$。

记录每一个数的下标 ， 从小到大每一次取值都把相应的数=0，多了个山峰就把初始解++，融合了两个山峰为一个就 --

#include <iostream>
#include <algorithm>
#include <cstring>
#include <set>using namespace std;const int N = 5e5 + 10;
int n, A[N], res;
set<int>a;
vector<int>h[N];int main(){cin >> n;for(int i = 1; i <= n; i ++){cin >> A[i];h[A[i]].push_back(i);//存储A中每一个数所出现的位置,以便后续直接访问a.insert(A[i]);//去重排序}int p = 1 , ans = 0;for(int i = 1 ; i <= n ; i++) if(!A[i - 1] && A[i]) ans ++ ;for(auto t : a){for(int j = p; j <= t; j ++){for(auto x : h[j]) {A[x] = 0;if(A[x-1] != 0 && A[x+1] != 0)ans ++; //多了个岛，++else if(A[x - 1] == 0 && A[x + 1] == 0 ) ans --;//少了个岛 --//其余的情况不变}}res = max(res, ans);p = t + 1;}cout << res;return 0;}

4. 收集卡牌

小林在玩一个抽卡游戏，其中有 $n$ 种不同的卡牌，编号为 $1$ 到 $n$。

每一次抽卡，她获得第 $i$ 种卡牌的概率为 $p_i$。

如果这张卡牌之前已经获得过了，就会转化为一枚硬币。

可以用 $k$ 枚硬币交换一张没有获得过的卡。

小林会一直抽卡，直至集齐了所有种类的卡牌为止，求她的期望抽卡次数。

如果你给出的答案与标准答案的绝对误差不超过 $10^{-4}$，则视为正确。

提示：聪明的小林会把硬币攒在手里，等到通过兑换就可以获得剩余所有卡牌时，一次性兑换并停止抽卡。

输入格式

输入共两行。

第一行包含两个用空格分隔的正整数 $n,k$，第二行给出 $p_1,p_2,\dots ,p_n$，用空格分隔。

输出格式

输出共一行，一个实数，即期望抽卡次数。

数据范围

对于 $20\%$ 的数据，保证 $1\le n,k\le 5$。
对于另外 $20\%$ 的数据，保证所有 $p_i$ 是相等的。
对于 $100\%$ 的数据，保证 $1\le n\le 16,1\le k\le 5$，所有的 $p_i$ 满足 $p_i\ge \frac{1}{10000}$，且 ${\sum }_{i=1}^n{p}_i=1$。
注意，本题在官网必须保留 $10$ 位小数才能通过（可能是没加SPJ），在本网站无此问题，只要满足你给出的答案与标准答案的绝对误差不超过 $10^{-4}$，则视为正确。

输入样例1：

2 2
0.4 0.6

输出样例1：

2.52

样例1解释

共有 $2$ 种卡牌，不妨记为 $A$ 和 $B$，获得概率分别为 $0.4$ 和 $0.6$，$2$ 枚硬币可以换一张卡牌。下面给出各种可能出现的情况：

• 第一次抽卡获得 $A$，第二次抽卡获得 $B$，抽卡结束，概率为 $0.4\times 0.6=0.24$，抽卡次数为 $2$。
• 第一次抽卡获得 $A$，第二次抽卡获得 $A$，第三次抽卡获得 $B$，抽卡结束，概率为 $0.4\times 0.4\times 0.6=0.096$，抽卡次数为 $3$。
• 第一次抽卡获得 $A$，第二次抽卡获得 $A$，第三次抽卡获得 $A$，用硬币兑换 $B$，抽卡结束，概率为 $0.4\times 0.4\times 0.4=0.064$，抽卡次数为 $3$。
• 第一次抽卡获得 $B$，第二次抽卡获得 $A$，抽卡结束，概率为 $0.6\times 0.4=0.24$，抽卡次数为 $2$。
• 第一次抽卡获得 $B$，第二次抽卡获得 $B$，第三次抽卡获得 $A$，抽卡结束，概率为 $0.6\times 0.6\times 0.4=0.144$，抽卡次数为 $3$。
• 第一次抽卡获得 $B$，第二次抽卡获得 $B$，第三次抽卡获得 $B$，用硬币兑换 $A$，抽卡结束，概率为 $0.6\times 0.6\times 0.6=0.216$，抽卡次数为 $3$。

因此答案是 $0.24\times 2+0.096\times 3+0.064\times 3+0.24\times 2+0.144\times 3+0.216\times 3=2.52$。

输入样例2：

4 3
0.006 0.1 0.2 0.694

输出样例2：

7.3229920752

先想到用暴搜，能够过20%
想到要加上记忆化好像会好一点，下面是记忆化满分代码

#include<bits/stdc++.h>
using namespace std;const int N = 20;
const int M = 1<<16 +5;
const int K = 100;
float A[N];
float state[M][K];
int  n,k;
float eps = 1e-5;int get(int num)
{int cnt = 0;while(num){num &= (num - 1);cnt ++;}return n - cnt;
}float dfs(int res  = 0, int n_coin = 0 , int cnt = 0)
{// 需要状态压缩,不能直接传数组（2^16可以存下）if(state[res][n_coin]) return state[res][n_coin];if(get(res) * k <= n_coin )  return  cnt;//cout<<p<<' ' <<get(res)<< " " << n_coin << ' '<<cnt <<endl; float temp = 0.0;for (int i = 1; i <= n; i ++ ){int j = 1<<i;if(res & j) temp +=A[i] * dfs(res , n_coin + 1 ,cnt + 1); // ?为什么A[i]移出去就对了else temp +=A[i] *dfs( res|j , n_coin , cnt + 1);}return state[res][n_coin] = temp;
}int main()
{scanf("%d%d", &n, &k);for (int i = 1; i <= n; i ++ ){scanf("%f", &A[i]);}printf("%.10f" , dfs());return 0;
}

但是我最开始的时候写的是下面的代码，只能过30%,代码只dfs里面传递的参数不同，不知道为什么错了，有知道的小伙伴，可以在评论区留言

#include<bits/stdc++.h>
using namespace std;const int N = 20;
const int M = 1<<16 +5;
const int K = 100;
float A[N];
float state[M][K];
int  n,k;
float eps = 1e-5;int get(int num)
{int cnt = 0;while(num){num &= (num - 1);cnt ++;}return n - cnt;
}float dfs(float p  = 1.0,int res  = 0, int n_coin = 0 , int cnt = 0)
{// 需要状态压缩,不能直接传数组（2^16可以存下）float temp = 0;for (int i = 1; i <= n; i ++ ){if(state[res][n_coin]){return state[res][n_coin];}if(get(res) * k <= n_coin ) {return state[res][n_coin] = p * cnt;}int j = 1<<i;if(res & j) temp += dfs(p * A[i] ,res , n_coin + 1 ,cnt + 1);else temp +=dfs(p * A[i] , res + j , n_coin , cnt + 1);}return state[res][n_coin] = temp;
}int main()
{scanf("%d%d", &n, &k);for (int i = 1; i <= n; i ++ ){scanf("%f", &A[i]);}printf("%.10f" , dfs());return 0;
}

我明白了，见上图（样例里的），存在在结束的时候，状态和硬币数量相同但是概率不同的情况，所以不传递概率更好。