本文主要是介绍Sort It (树状数组+dp)，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
| 主页 | 讨论版 | 问题 | 名次 | 状态 | 统计 |
问题 F: Sort It
时间限制: 6 Sec 内存限制: 128 MB提交: 30 解决: 8
[ 提交][ 状态][ 讨论版]
题目描述
You are given a permutation of length n:p1,p2,...pn.Consider arrays of length n with possibly equal number from 1 to n.
If after rearrange elements of the array in the order of “all numbers equal to p1,all numbers equal to p2...all numbers equal to pn”,
the array become non-decreasing,then we call the array is sortable by p.
Calculate the total number of arrays that are sortable by p.
As the answer can be very large,output it after module 1e9+7.
输入
Several test cases.
The first line contains a single integer n(1<=n<=2000),the length of permutation.
The second line contains n distinct integers p1,p2,..pn(1<=pi<=n).
输出
Output a singe number -- the answer to the problem module 1e9+7.
样例输入
22 132 1 3 样例输出
215 提示
All Copyright Reserved 2010-2015 NEU-ACM TEAM
GPL2.0 2003-2013 HUSTOJ Project TEAM
/*
给一个排列p,问有多少个长度为n的序列(都是1到n的数)可以用p排序,p排序定义为先将序列中p1的取出来,再取p2,一直取到pn,
可以发现一个序列能否被p排序,只和序列出现了那些数有关,具体的来说就是序列中出现的数必须能在排列中找到这个LIS,
f[i]表示用i个数构成n个数的排列有多少个,g[i]表示长度为i的LIS有多少种,则答案是f[i]*g[i]的和,代码如下*/
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn = 2e3 + 10;
const int mod = 1e9 + 7;
int f[maxn][maxn],n;
int p[maxn],g[maxn][maxn];
int dp[maxn][maxn];
void init(int n)
{memset(f,0,sizeof f);f[0][0] = 1;for(int i = 1; i <= n; ++i) {for(int j = 1; j <= i; ++j) {f[i][j] = (f[i-1][j-1]+f[i-1][j])*(j+0LL) % mod;}}
}
int lowbit(int x)
{return x & -x;
}
void add(int *c,int x,int d,int n)
{for(; x <= n; x += lowbit(x)) c[x] = (c[x] + d) % mod;
}
int query(int *c,int x)
{int retVal = 0;for(;x > 0; x -= lowbit(x)) retVal = (retVal + c[x]) % mod;return retVal;
}int main()
{init(2000);int n;while(scanf("%d",&n)==1) {for(int i = 1; i <= n; ++i) scanf("%d",p+i);memset(g,0,sizeof g);for(int i = 1; i <= n; ++i) {int x = p[i];for(int j = 1; j <= i; ++j) {int ret = (j == 1 ? 1 : query(g[j-1],x-1));add(g[j],x,ret,n);g[0][j] += ret;g[0][j] %= mod;}}int ans = 0;for(int i = 1; i <= n; ++i) {int add = g[0][i]*(f[n][i]+0LL) % mod;ans = (ans + add) % mod;}printf("%d\n",ans);}return 0;
}
这篇关于Sort It (树状数组+dp)的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
