「FSLOI Round I」山峦 题解
FL_sleake
·
·
题解
解题思路
Subtask 1
```cpp
#include<bits/stdc++.h>
using namespace std;
#define int long long
int n,a[510],ans=0;
int b[510],cnt=0;
int c[510],ct=0;
bool check(){
ct=0;
if(cnt<3) return 0;//长度不到3
if(b[1]>=b[2]) return 0;//开头不满足
if(b[cnt]>=b[cnt-1]) return 0;//结尾不满足
for(int i=1;i+2<=cnt;i++){
//如果有连续三个数相同，必定不满足
if(b[i]==b[i+1]&&b[i+1]==b[i+2]) return 0;
}
int id=1;
while(id<cnt){
while(id+1<=cnt&&b[id+1]>b[id]) id++;//找上升段
c[++ct]=id;//记录
if(b[id+1]==b[id]) return 0;
//注意上升段的后一位不严格小于当前位则不满足
//比如 1,2,3,3,2
while(id+1<=cnt&&b[id+1]<b[id]) id++;//找下降段
if(b[id]==b[id+1]) id++;
//注意此时相等需要手动往后走一位
//比如 2,4,2,2,5,2
}
//山峰高度不递增则不满足
for(int i=1;i<ct;i++) if(b[c[i]]>=b[c[i+1]]) return 0;
//间隔小于2则不能拆分成山峰
for(int i=1;i<ct;i++) if(c[i+1]-c[i]<=2) return 0;
return 1;
}
signed main(){
cin>>n;
for(int i=0;i<n;i++) cin>>a[i];
int num=0;
for(int i=0;i<(1ll<<n);i++){
//枚举所有子序列
cnt=0;
for(int j=0;j<n;j++) if((i>>j)&1) b[++cnt]=a[j];
if(check()) ans++;
}
cout<<ans<<endl;
return 0;
}
```
#### Subtask 2 & 3 & 4 & 5
考虑 dp。我们考虑先去掉山峦的最后一段连续下降段。比如对于 $1,2,3,4,3,2,1$，我们暂且认为 $1,2,3,4$ 是合法的一段。再记山峰的高度所在位置为**山顶**。记 $dp_i$ 表示以 $i$ 为最后一个**山顶**，前 $i$ 位有多少合法子序列。
考虑预处理出两个二维数组 $f1,f2$。
$f1_{i,j}$ 表示以 $i$ 为山顶，以 $j$ 为结尾的下降段的数量。
$f2_{i,j}$ 表示以 $i$ 为山顶，以 $j$ 为开头的上升段的数量。
这样的话 $f1,f2$ 都可以在 $\Theta(n^3)$ 复杂度内预处理出来。代码如下：
```cpp
for(int i=1;i<=n;i++){
f1[i][i]=1;
for(int j=i+1;j<=n;j++){
for(int k=i;k<=j-1;k++){
if(a[k]>a[j]) f1[i][j]=(f1[i][j]+f1[i][k])%mod;
}
}
}
for(int i=n;i>=1;i--){
f2[i][i]=1;
for(int j=i-1;j>=1;j--){
for(int k=j+1;k<=i;k++){
if(a[k]>a[j]) f2[i][j]=(f2[i][j]+f2[i][k])%mod;
}
}
}
```
接下来就可以对 $dp$ 数组进行初始化了：
$$dp_i=\sum_{j=1}^{i-1}f2_{i,j}$$
然后考虑转移。枚举两个山顶 $i,j$，不妨 $i>j$，那么 $dp_i=dp_i+dp_j\times num$，其中 $num$ 表示 $j$ 到 $i$ 这一段中有多少个子序列满足如果 $1$ 到 $j$ 合法，则 $1$ 到 $i$ 合法。感性理解一下就是求 $j$ 到 $i$ 之间有多少个“山谷”。此处“山谷”表示先下降后上升的子序列。
那么如何求 $num$ 呢？考虑枚举“谷底”。因为山谷满足先单调递减再单调递增，那么不同的“谷底”一定对应不同的山谷（先不考虑数字相同的情况）。假设当前枚举的谷底下标为 $k$，则合法的山谷有 $f1_{j,k}\times f2_{i,k}-1$ 个。其实就是 $j$ 到 $k$ 需要下降，$k$ 到 $i$ 需要上升。那么减一是什么呢？减一是形如 $\cdots,3,2,4$ 这种情况，其中 $3,4$ 为当前枚举的山顶，$2$ 为当前枚举的谷底。也就是说，不能单独地只选择一个谷底。
接下来我们再考虑相等的数。比如 $\cdots,3,2,2,4$ 是合法的。此时产生的山谷应该是 $f1_{j,k_1}\times f2_{i,k_2}$ 个，其中 $k_1,k_2$ 满足 $a_{k_1}=a_{k_2}$ 且 $k_1 < k_2$。我们发现暴力枚举 $k_1,k_2$ 算的话复杂度是 $\Theta(n^2)$，但是外面已经有了一个 $\Theta(n^2)$ 了，所以需要优化掉一个 $n$。当然 Subtask 2 此时可以过了。
上述中 $k_2$ 产生的贡献应该是与前面一堆 $k_1$ 相乘之和，那不就是与前面一堆 $k_1$ 之和相乘吗！于是开一个数组 $sum$ 记录 $f1_{j,k_1}$ 之和即可。到此为止，我们就求出来了 $num$，代码如下：
```cpp
int solve(int l,int r){
int ans=0;
for(int i=l+1;i<=r-1;i++){
if(f1[l][i]&&f2[r][i]) ans=(ans+f1[l][i]*f2[r][i]%mod-1+mod)%mod;
ans=(ans+sum[a[i]]*f2[r][i]%mod)%mod;
sum[a[i]]=(sum[a[i]]+f1[l][i])%mod;
}
for(int i=l+1;i<=r-1;i++) sum[a[i]]=0;
return ans;
}
```
到此为止，$dp_i$ 就可以求出来了。注意开头所说的 $dp_i$ 的定义，我们应该在 $i$ 后面再接上一段下降段，才是真正的山峦。这里再用一步乘法原理就可以统计出最终答案了：
```cpp
int ans=0;
for(int i=1;i<=n;i++){
int Sum=0;
for(int j=i+1;j<=n;j++) Sum=(Sum+f1[i][j])%mod;
ans=(ans+Sum*dp[i]%mod)%mod;
}
cout<<ans<<endl;
```
### 代码示例
```cpp
#include<bits/stdc++.h>
using namespace std;
#define int long long
const int mod=998244353;
int n,a[510],f1[510][510]={0},f2[510][510]={0},dp[510]={0};
int sum[1000010];
int solve(int l,int r){
int ans=0;
for(int i=l+1;i<=r-1;i++){
if(f1[l][i]&&f2[r][i]) ans=(ans+f1[l][i]*f2[r][i]%mod-1+mod)%mod;
ans=(ans+sum[a[i]]*f2[r][i]%mod)%mod;
sum[a[i]]=(sum[a[i]]+f1[l][i])%mod;
}
for(int i=l+1;i<=r-1;i++) sum[a[i]]=0;
return ans;
}
signed main(){
cin>>n;
for(int i=1;i<=n;i++) cin>>a[i];
for(int i=1;i<=n;i++){
f1[i][i]=1;
for(int j=i+1;j<=n;j++){
for(int k=i;k<=j-1;k++){
if(a[k]>a[j]) f1[i][j]=(f1[i][j]+f1[i][k])%mod;
}
}
}
for(int i=n;i>=1;i--){
f2[i][i]=1;
for(int j=i-1;j>=1;j--){
for(int k=j+1;k<=i;k++){
if(a[k]>a[j]) f2[i][j]=(f2[i][j]+f2[i][k])%mod;
}
}
}
for(int i=1;i<=n;i++){
for(int j=1;j<=i-1;j++) dp[i]=(dp[i]+f2[i][j])%mod;
}
for(int i=1;i<=n;i++){
for(int j=1;j<=i-3;j++){
if(a[j]>=a[i]) continue;
dp[i]=(dp[i]+dp[j]*solve(j,i)%mod)%mod;
}
}
int ans=0;
for(int i=1;i<=n;i++){
int Sum=0;
for(int j=i+1;j<=n;j++) Sum=(Sum+f1[i][j])%mod;
ans=(ans+Sum*dp[i]%mod)%mod;
}
cout<<ans<<endl;
return 0;
}
```