杭电多校第10场 6880 Permutation Counting（DP）

本文主要是介绍杭电多校第10场 6880 Permutation Counting（DP），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

Problem Description
For a given permutation a1,a2,⋯,an of length n, we defined the neighbor sequence b of a, the length of which is n−1, as following:

bi={01ai<ai+1ai>ai+1
.

For example, the neighbor sequence of permutation 1,2,3,6,4,5 is 0,0,0,1,0.

Now we give you an integer n and a sequence b1,b2,⋯,bn−1 of length n−1, you should calculate the number of permutations of length n whose neighbor sequence equals to b.

To avoid calculation of big number, you should output the answer module 109+7.

Input
The first line contains one positive integer T (1≤T≤50), denoting the number of test cases. For each test case:

The first line of the input contains one integer n,(2≤n≤5000).

The second line of the input contains n−1 integer: b1,b2,⋯,bn−1

There are no more than 20 cases with n>300.

Output
For each test case:

Output one integer indicating the answer module 109+7.

Sample Input
2
3
1 0
5
1 0 0 1

Sample Output
2
11

题意：
求多少种前n个数的排列符合题目中的限制

思路：
定义$f[i][j]$为考虑了前$i$个数的排列，第$i$个位置放的数在前$i$个数中为$j$的小方案数。
那么如果$a[i]>a[i-1]，$也就是$b[i-1]=0$。
$f[i][j]=\sum f[i-1][k]，1\le k\le j-1$
$j$可以等于$k$，因为前$i$个数的第$j$小一定小于前$i-1$个数的第$j$小。下面$j$可以等于$k$同理。

如果$a[i]<a[i-1]，$也就是$b[i-1]=1$。
$f[i][j]=\sum f[i-1][k]，j\le k\le i-1$

#include <cstdio>
#include <cstring>
#include <algorithm>using namespace std;typedef long long ll;
const int maxn = 5005;
const int mod = 1e9 + 7;ll f[maxn][maxn];
int a[maxn];int main() {int T;scanf("%d",&T);while(T--) {int n;scanf("%d",&n);for(int i = 1;i <= n;i++) {for(int j = 1;j <= n;j++) {f[i][j] = 0;}}for(int i = 1;i < n;i++) scanf("%d",&a[i]);f[1][1] = 1;for(int i = 2;i <= n;i++) {ll sum = 0;if(a[i - 1] == 0) { //a[i]>a[i-1]for(int j = 1;j <= i;j++) {f[i][j] = sum;sum = (sum + f[i - 1][j]) % mod;}} else { //a[i]<a[i-1]for(int j = i - 1;j >= 1;j--) {sum = (sum + f[i - 1][j]) % mod;f[i][j] = sum;}}}ll ans = 0;for(int i = 1;i <= n;i++) {ans = (ans + f[n][i]) % mod;}printf("%lld\n",ans);}return 0;
}

这篇关于杭电多校第10场 6880 Permutation Counting（DP）的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---