\(\text{CF1859E}\)
有两个长度为 \(n\) 的序列 \(a\)，\(b\)。其中区间 \([l,r]\)，\((1 \le l \le r \le n)\) 的价值是 \(|b_l-a_r|+|b_r-a_l|\)。
区间 \([l_1,r_1]\) \((1 \le l_1 \le r_1 \le n)\) 和区间 \([l_2,r_2]\) \((1 \le l_2 \le r_2 \le n)\) 不相交，是指 \(r_1 < l_2\) 满足或 \(r_2 < l_1\) 满足。
区间 \([l,r]\) \((1 \le l \le r \le n)\) 的长度被定义为 \(r-l+1\)。
给定 \(a,b\)，求若干个互不相交的，总长度为 \(k\) 的 \([l,r]\) 的价值总和的最大值。
思路点拨
我们考虑一个 \(O(nk^2)\) 的暴力动态规划。我们定义状态 \(f_{i,j}\) 表示目前考虑到 \(i\) ，选了的长度为 \(j\) 的最大值。转移分两类讨论：
-
不选择 \(i\) , 那么 \(f_{i,j}=f_{i-1,j}\) 。
-
选择 \(i\) ，枚举 \(i\) 所属这一段的长度， \(f_{i,j}=\max_{mid=1}^k\{f_{i-mid,j-mid}+|b_{mid+1}-a_i|+|b_i-a_{mid+1}|\}\) 。
考虑优化，这里需要运用一种动态规划中常用的技巧：拆分绝对值。
我们将转移分为四类讨论：
Q:这样难道就不需要考虑 \(a_l,a_r,b_l,b_r\) 的大小关系吗？不会算多或者算少吗？
A:并不会，因为绝对值有性质：\(X \leqslant |X|\) 。所以我们这样计算肯定包含最优解并且不会多计算贡献只会少计算（不影响答案）。
对于上述的转移，我们将包含 \(a_i,b_i\) 的式子合并，整理得到：
因为 \(a_i-b_i\) 一类的式子是必须要加上的，我们无须考虑，对于剩下的部分，可以记录 \(dp_{len,0/1/2/3}\) 作为前缀最大值优化转移。
for(int i=1;i<=n;i++)
for(int j=1;j<=min(i,k);j++){
dp[i][j]=dp[i-1][j];
f[i-j][0]=max(f[i-j][0],dp[i-1][j-1]+a[i]+b[i]);
f[i-j][1]=max(f[i-j][1],dp[i-1][j-1]-a[i]+b[i]);
f[i-j][2]=max(f[i-j][2],dp[i-1][j-1]+a[i]-b[i]);
f[i-j][3]=max(f[i-j][3],dp[i-1][j-1]-a[i]-b[i]);
dp[i][j]=max(dp[i][j],f[i-j][0]-a[i]-b[i]);
dp[i][j]=max(dp[i][j],f[i-j][1]-a[i]+b[i]);
dp[i][j]=max(dp[i][j],f[i-j][2]+a[i]-b[i]);
dp[i][j]=max(dp[i][j],f[i-j][3]+a[i]+b[i]);
}
\(\text{CF1858D}\)
现在有一个长度为 \(n\) 的序列，每一个位置山过的元素 \(a_i \in \{0,1\}\) 。现在你有至多 \(k\) 次机会修改一个位置上的值， \(0\) 变成 \(1\) ，\(1\) 变成 \(0\) 。假设 \(k\) 次操作之后最长的连续 \(1\) 的长度为 \(l_1\), 最长的连续 \(0\) 长度为 \(l_0\) 。对于每一个常数 \(z \in[1,n]\) ，求出 \(z\times l_0+l_1\) 的最大值。
思路点拨
发现产生贡献的两端 \(0\) 或者 \(1\) 不会相交，所以我们可以记录前缀和后缀的信息。定义状态：
-
\(pre0[i][j]\) 表示考虑到前缀 \(i\) ，修改了 \(j\) 次之后最长 \(0\) 可以是多少。
-
\(pre1[i][j]\) 表示考虑到前缀 \(i\) ，修改了 \(j\) 次之后最长 \(1\) 可以是多少。
-
\(suc0[i][j]\) 表示考虑到后缀 \(i\) ，修改了 \(j\) 次之后最长 \(0\) 可以是多少。
-
\(suc1[i][j]\) 表示考虑到后缀 \(i\) ，修改了 \(j\) 次之后最长 \(1\) 可以是多少。
如果可以求出来，最后通过一些手段合并答案就可以了。
转移也比较简单：
我们可以对上述四个数组做二维前缀最大值，数组的意义将转变为：
-
\(pre0[i][j]\) 表示考虑到前缀 \(1,2,...i\) ，修改了 \(j\) 次之后最长 \(0\) 可以是多少。
-
\(pre1[i][j]\) 表示考虑到前缀 \(1,2,...i\) ，修改了 \(j\) 次之后最长 \(1\) 可以是多少。
-
\(suc0[i][j]\) 表示考虑到后缀 \(i,i+1,...,n\) ，修改了 \(j\) 次之后最长 \(0\) 可以是多少。
-
\(suc1[i][j]\) 表示考虑到后缀 \(i,i+1,...,n\) ，修改了 \(j\) 次之后最长 \(1\) 可以是多少。
现在我们如果枚举一个常数 \(z\) ，再枚举一个最长 \(0\) 和最长 \(O(n^3)\) 的时间求出解。但是我们发现这个过程十分的重复，我们考虑优化。
定义 \(mx_i\) 表示当最长 \(l_0\) 为 \(i\) 时， \(l_1\) 的最大可能值。转移显然：
可以看见，转移的时间等于 \(pre0,suc0\) 的状态数量，也就是 \(O(n^2)\) 。
每一次我们枚举一个常数 \(z\) ，答案就是 \(\max_{i=1}^k mx_i+i\times z\) 。
for(int i=1;i<=n;i++){
pre0[i][0]=(a[i]==1)?0:pre0[i-1][0]+1;
for(int j=1;j<=min(i,k);j++)
pre0[i][j]=(a[i]==1)?pre0[i-1][j-1]+1:pre0[i-1][j]+1;
pre1[i][0]=(a[i]==0)?0:pre1[i-1][0]+1;
for(int j=1;j<=min(i,k);j++)
pre1[i][j]=(a[i]==0)?pre1[i-1][j-1]+1:pre1[i-1][j]+1;
}
for(int i=n;i;i--){
suc0[i][0]=(a[i]==1)?0:suc0[i+1][0]+1;
for(int j=1;j<=min(n-i+1,k);j++)
suc0[i][j]=(a[i]==1)?suc0[i+1][j-1]+1:suc0[i+1][j]+1;
suc1[i][0]=(a[i]==0)?0:suc1[i+1][0]+1;
for(int j=1;j<=min(n-i+1,k);j++)
suc1[i][j]=(a[i]==0)?suc1[i+1][j-1]+1:suc1[i+1][j]+1;
}
for(int i=1;i<=n;i++){
for(int j=0;j<=k;j++){
pre0[i][j]=max(pre0[i][j],pre0[i-1][j]);
pre1[i][j]=max(pre1[i][j],pre1[i-1][j]);
}
}
for(int i=n;i;i--){
for(int j=0;j<=k;j++){
suc0[i][j]=max(suc0[i][j],suc0[i+1][j]);
suc1[i][j]=max(suc1[i][j],suc1[i+1][j]);
}
}
for(int i=1;i<=n;i++){
for(int j=1;j<=k;j++){
pre0[i][j]=max(pre0[i][j],pre0[i][j-1]);
pre1[i][j]=max(pre1[i][j],pre1[i][j-1]);
suc0[i][j]=max(suc0[i][j],suc0[i][j-1]);
suc1[i][j]=max(suc1[i][j],suc1[i][j-1]);
}
}
memset(mx,-1,sizeof(mx));
for(int i=1;i<=n;i++){
for(int j=0;j<=k;j++)
mx[pre0[i][j]]=max(mx[pre0[i][j]],suc1[i+1][k-j]);
for(int j=0;j<=k;j++)
mx[suc0[i][j]]=max(mx[suc0[i][j]],pre1[i-1][k-j]);
}
mx[0]=max(mx[0],pre1[n][k]);
for(int i=1;i<=n;i++){
int ans=0;
for(int j=0;j<=n;j++)
if(mx[j]!=-1) ans=max(ans,j*i+mx[j]);
cout<<ans<<" ";
}
\(\text{CF1854C}\)
给定大小为 \(n\) 的正整数集合 \(S\)，\(S\) 中的每个数在 \(1\sim m\) 之间。
每一秒进行如下操作：
- 从 \(S\) 中等概率随机选择一个数 \(x\)。
- 将 \(x\) 从 \(S\) 中删去。
- 若 \(x + 1\leq m\) 且 \(x + 1\notin S\)，则将 \(x + 1\) 加入 \(S\)。
求 \(S\) 变成空集的期望时间，对 \(10 ^ 9 + 7\) 取模。
\(1\leq n\leq m \leq 500\)，\(1\leq S_1 < S_2 < \cdots < S_n \leq m\)。
思路点拨
如果去除第三点限制中的 \(x+1\notin S\) ，那么答案就是 \(\sum (m-S_i+1)\) 。现在考虑如果有这种情况怎么办。因为 \(1\leq S_1 < S_2 < \cdots < S_n \leq m\) ，所以如果发生 \(x+1 \in S\) 的情况，也只会在相邻两项之间发生。根据期望的线性性质，我们可以对于相邻两项分别考虑，对于 \(S_i,S_{i+1}\) ：
我们定义状态 \(f_{a,b}\) 表示 \(S_i=a,S_{i+1}=b\) 的概率是多少，边界条件就是 \(f_{S_i.S_{i+1}}=1\) 。转移填表刷表都可以,这里给出刷表：
这里讲一下为什么只乘上 \(\dfrac{1}{2}\) ，难道不需要考虑其他元素的选择吗？我们讲到，我们根据线性性质转化为了相邻两项之间的贡献，那么这个子问题不需要考虑其余元素，由于 \(S_i,S_{i+1}\) 会被等概率选中，所以乘上 \(\dfrac{1}{2}\) 。\(S_i,S_{i+1}\) 的贡献就是 \(\sum f_{i,j}\times (m-i+1)\) 。这个时候一个元素 \(S=i\) 原来会产生 \((m-i+1)\) 的贡献，但是因为他与另一个元素相同了，所以不可以继续产生贡献，被我们多算了。
现在的时间复杂度是 \(O(nm^2)\) ，的确可以通过，但是我们有更加优秀的做法。还是由于期望的线性性质，我们可以将全部的动态规划一起运算，并不会引起答案错误，时间复杂度就是 \(O(m^2)\) 。