DP题好多ya :(
# 题面
> Linked Codeforces 1383E
点击展开/折叠题面
给定一个01串 $S$（$|S|\le10^6$），你可以进行任意次操作，每次选择相邻的两个位置 $i,i+1$，用 $\max\{S_i,S_{i+1}\}$ 替换 $S_i,S_{i+1}$。
求能够得到多少种不同的01串。
# 解析
如果 $S$ 中原本就有 $1$，那么任何一个可以得到的 01 串都可以看作是 $1$“吞并”了旁边的 $0$ 得到的。（如果没有 $1$ 就特判一下）
设 $S$ 的最左端有连续的 $a$ 个 $0$，那么我们可以先将这些 $0$ 删去后求得答案 $x_0$。此时求得的 01 串的左边一定是 $1$，所以可以将所得的每个 01 串左端加上 $0\sim a$ 个 $0$ 得到不同的 01 串。于是最终答案就是 $ax_0$。
考虑当前的 $S$ 左端是 $1$，求 $x_0$。于是可以设计DP，对于原串中的每个 $1$，决策它向右合并后在右边剩下了多少连续的 $0$。定义状态 $f_i$ 表示原串的第 $i$ 个 $1$ 为开头的后缀能够得到多少种 01 串。假如现在要计算原串的第 $i$ 个 $1$ 向右合并后，右边有 $j$ 个连续的 $0$，我们需要找到原串中在 $i$ 之后的第一次出现的连续的 $j$ 个 $0$，从下一个 $1$ 的位置 $k$ 转移过来。其中“第一次出现”保证了能够构造出尽可能多的 01 串。
但是还有一种特殊情况，设 $S$ 的右端有 $b$ 个连续的 $0$：将第 $i$ 个 $1$ 之后的 $1$ 全部合并，然后再在末尾留下 $0\sim b$ 个 $0$。
于是可以得到DP转移式：
其中的 $k$ 是找到的第一个前面有至少 $j$ 个连续的 $0$ 的 $1$ 的标号。
我们发现，如果 $p,q$ 满足 $p<q$ 且 $p$ 前面连续的 $0$ 的个数大于等于 $q$ 前面连续的 $0$ 的个数，那么 $q$ 永远不会成为转移点 $k$。于是可以用单调栈维护。
# 源代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
|
#include<stack>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int N=1e6+10,MOD=1e9+7;
#define ci const int &
#define val(i) (pos[i]-pos[(i)-1])
inline int Add(ci a,ci b){return a+b>=MOD? a+b-MOD:a+b;}
inline int Sub(ci a,ci b){return a-b<0? a-b+MOD:a-b;}
inline int Mul(ci a,ci b){return int(1ll*a*b%MOD);}
char str[N];
int pos[N],f[N];
int n,m;
stack<int> stk;
int main(){
scanf("%s",str+1);
n=(int)strlen(str+1);
for(int i=1;i<=n;i++)
if(str[i]=='1')
pos[++m]=i;
if(!m){printf("%d\n",n);return 0;}
stk.push(m);
int sufextra=n-pos[m]+1,preextra=pos[1];
f[m]=sufextra;
int tot=Mul(val(m),f[m]);
for(int i=m-1;i>=1;i--){
f[i]=Add(tot,sufextra);
int las=0,vali=val(i);
while(!stk.empty() && vali>=val(stk.top())){
int j=stk.top(),valj=val(j);
tot=Sub(tot,Mul(Sub(valj,las),f[j]));
las=valj;
stk.pop();
}
if(!stk.empty()){
int j=stk.top(),valj=val(j);
tot=Sub(tot,Mul(Sub(valj,las),f[j]));
tot=Add(tot,Mul(Sub(valj,vali),f[j]));
}
tot=Add(tot,Mul(vali,f[i]));
stk.push(i);
}
printf("%d\n",Mul(f[1],preextra));
return 0;
}
|
THE END
Thanks for reading!
> Linked 象牙塔少女 αrtist5-网易云