[Hihocoder1596] Beautiful Sequence

qwq

题意

n个数随机打乱,求形成凹函数的方案数。

思路

先离散化。

考虑从小到大加。

$ f[i][x][y][z][w] $表示考虑到第i个数,两边次小值x,y,上个元素在w的那一边,上个元素放的另一边最大值为z。

暴力转移。

可以加滚动数组。

Code

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
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cctype>
inline int getint()
{
int r = 0,s = 1;char c = getchar();for(;!isdigit(c);c = getchar()) if(c == '-') s = 0;
for(;isdigit(c);c = getchar()) r = (((r << 2) + r) << 1) + (c ^ '0');return s ? r : -r;
}
const int N = 65,MOD = 1000000007;
int a[N],n,b[N],m;
int f[2][N][N][N][2];
inline void U(int &x,int y){if((x += y) >= MOD) x -= MOD;}
inline int judge(int x,int y,int z){return (2 * b[y] <= b[x] + b[z]);}
int main()
{
m = n = getint();
for(int i = 1;i <= n;i++) b[i] = a[i] = getint();
std::sort(b + 1,b + n + 1);
m = std::unique(b + 1,b + n + 1) - b - 1;
for(int i = 1;i <= n;i++) a[i] = std::lower_bound(b + 1,b + m + 1,a[i]) - b;
std::sort(a + 1,a + n + 1);
int cnt = 1,frc = 1;
for(;cnt <= n && a[cnt] == a[1];cnt++) frc = 1LL * frc * cnt % MOD;
f[(--cnt) & 1][a[1]][a[1]][a[1]][0] = frc;
for(int i = cnt;i < n;i++)
{
int u = i & 1,v = u ^ 1;
memset(f[v],0,sizeof(f[v]));
for(int x = 1;x <= m;++x) for(int y = 1;y <= m;++y) for(int z = 1;z <= m;++z)
{
if(judge(x,a[i],a[i + 1])) U(f[v][a[i]][y][z][0],f[u][x][y][z][0]);
if(judge(y,z,a[i + 1])) U(f[v][x][z][a[i]][1],f[u][x][y][z][0]);
if(judge(x,z,a[i + 1])) U(f[v][z][y][a[i]][0],f[u][x][y][z][1]);
if(judge(y,a[i],a[i + 1])) U(f[v][x][a[i]][z][1],f[u][x][y][z][1]);
}
}
int ans = 0,u = n & 1;
for(int x = 1;x <= m;++x) for(int y = 1;y <= m;++y) for(int z = 1;z <= m;++z) {U(ans,f[u][x][y][z][0]);U(ans,f[u][x][y][z][1]);}
printf("%d\n",ans);
return 0;
}