ps做的网站稿怎么做成网站,行业网站需要如何做,计算机软件开发是干什么的,营销类的网站解题思路 设置两个二维数组 $f$ 和 $g$#xff0c;含义如下。 $f[l][r]$ 表示在期望得到的队形中 $l\rightarrow r$ 这段区间初始队形排列的方案数#xff0c;并且最后一个加入进去的是第 $l$ 个人。 $g[l][r]$ 表示在期望得到的队形中 $l\rightarrow r$ 这段区间初始队形排列…解题思路 设置两个二维数组 $f$ 和 $g$含义如下。 $f[l][r]$ 表示在期望得到的队形中 $l\rightarrow r$ 这段区间初始队形排列的方案数并且最后一个加入进去的是第 $l$ 个人。 $g[l][r]$ 表示在期望得到的队形中 $l\rightarrow r$ 这段区间初始队形排列的方案数并且最后一个加入进去的是第 $r$ 个人。 那么可以看出来 $g[l][r]$ 可以从 $g[l][r-1]$ 跟新出来$f[l][r]$ 可以从 $f[l1][r]$ 跟新出来。 大致可以分为下面四种情况 现在决策的这个人插到队伍的最左边即当前这个人比前一个加入队列的要矮针对 $f[l][r]$ 前一个排进去的人是在第 $l1$ 的位置上$f[l1][r]\rightarrow a[l]a[l1]$前一个排进去的人是在第 $r$ 的位置上$g[l1][r]\rightarrow a[l]a[r]$现在决策的这个人插到队伍的最右边即当前这个人比前一个加入队列的要高针对 $g[l][r]$ 前一个排进去的人是在第 $l$ 的位置上$f[l][r-1]\rightarrow a[r]a[l]$前一个排进去的人是在第 $r-1$ 的位置上$g[l][r-1]\rightarrow a[r]a[r-1]$根据上面的关系就可以写出状态转移方程 记得要初始化 $lr$ 的数组还有就是枚举区间长度的时候从 $2$ 开始枚举否则会改变 之前初始化的数组造成答案出错 附上代码 #include iostream
#include cstring
#include cstdio
using namespace std;
const int maxn 1003, HA 19650827;
int n, f[maxn][maxn], g[maxn][maxn], a[maxn];
int main() {scanf(%d, n);for(int i1; in; i)scanf(%d, a[i]);for(int i1; in; i) f[i][i] 1;static int r;for(int i2; in; i) {for(int l1; li-1n; l) {r li-1;f[l][r] f[l1][r] * (a[l]a[l1]) % HA g[l1][r] * (a[l]a[r]) % HA;f[l][r] f[l][r] % HA;g[l][r] f[l][r-1] * (a[r]a[l]) % HA g[l][r-1] * (a[r]a[r-1]) % HA;g[l][r] g[l][r] % HA;}}printf(%d, (g[1][n]f[1][n]) % HA);
} 转载于:https://www.cnblogs.com/bljfy/p/9572712.html
