问题描述
A 同学的学习成绩十分不稳定，于是老师对他说：“只要你连续 4 天成绩有进步，那我就奖励给你一朵小红花。”

可是这对于 A 同学太困难了。于是，老师对他放宽了要求：“只要你有 4 天成绩是递增的，我就奖励你一朵小红花。

”即只要对于第 i、j、k、l 四天，满足 i < j < k < l 并且对于成绩 w_i < w_j < w_k < w_l，那么就可以得到一朵小红花的奖励。

现让你求出，A 同学可以得到多少朵小红花。

输入格式
第一行一个整数 n，表示总共有 n 天。
第二行 n 个数，表示每天的成绩 w_i。

输出格式
一个数，表示总共可以得到多少朵小红花。

样例输入
6
1 3 2 3 4 5

样例输出
6

数据范围
对于40%的数据，n ≤ 50；
对于100%的数据，n ≤ 2000，0 ≤ w_i ≤ 10⁹。

---

题解一
记忆化搜索：

#include <iostream>
#include <cstring>
using namespace std;typedef long long LL;const int N = 2020;int n;
LL s[N], f[N][N];LL dfs(int u, int num)
{if(num % 4 == 0) return 1;if(f[u][num] != -1) return f[u][num];f[u][num] = 0;for (int i = u + 1; i <= n; i ++)if(s[i] > s[u]) f[u][num] += dfs(i, num + 1);return f[u][num];	
}int main()
{cin >> n;for (int i = 1; i <= n; i ++) cin >> s[i];memset(f, -1, sizeof f);LL ans = 0;for (int i = 1; i <= n; i ++) ans += dfs(i, 1);cout << ans << endl;return 0;
}

题解二
动态规划：

f[i][j]：

• 集合：所有以 s[i] 为起点，递增序列长度为 j 的方案的集合
• 属性：数量

=>【比较详细的解释】<=

#include <iostream>
using namespace std;typedef long long LL;const int N = 2020;int n;
LL s[N], f[N][N];int main()
{cin >> n;for (int i = 1; i <= n; i ++) cin >> s[i], f[i][1] = 1;for (int i = n; i > 0; i --)for (int j = i + 1; j <= n; j ++)if(s[j] > s[i]){f[i][2] += f[j][1];f[i][3] += f[j][2];f[i][4] += f[j][3];}LL ans = 0;for (int i = 1; i <= n; i ++)ans += f[i][4];cout << ans << endl;return 0;			
}

ps：智商不够，题量来凑😭，每次遇到新的题型就傻眼了 (⊙﹏⊙)