51nod1296 有限制的排列递推+前缀和优化

1296 有限制的排列  题目来源：  HackerRank 基准时间限制：1 秒 空间限制：131072 KB 分值: 80  难度：5级算法题  收藏  关注 计算整数集合{1,2,3,4, .... N }满足下列条件的的排列个数: 在位置a1, a2, ..., aK小于其邻居（编号从0开始）。 在位置b1, b2, ..., bL大于其邻居。 输出符合条件的排列数量Mod 1000000007的结果。例如：N = 4，a = {1}, b = {2}，符合条件的排列为： 2 1 4 3 3 2 4 1 4 2 3 1 3 1 4 2 4 1 3 2 Input 第1行：3个数N, K, L，分别表示数组的长度，限制a的长度，限制b的长度(1 <= N <= 5000, 1 <= K, L <= N)。 第2 - K + 1行：每行一个数，对应限制a的位置(1 <= ai <= N - 2) 第K + 2 - K + L + 1行：每行一个数，对应限制b的位置(1 <= bi <= N - 2) Output 输出符合条件的排列数量Mod 1000000007的结果。 Input示例 4 1 1 1 2 Output示例

5

//要知道递推关系，首先需要知道怎么生成一个排列，如果之前有一个长度为n的排列，我们增加一位变成n+1位的话，那么我们只要考虑第n+1位是多少，若a[n+1]=x，那么我们只要将原来n个数的排列中的数字[x~n]都加上1，那么我们就把第n+1位插入到了排列中 //设dp[i][j]表示第i位为j时的符合所以条件的方案有多少种，且1~i就是区间[1,i]的一个排列，有这个为基础我们就能向i+1位递推了，然后根据第i+1位与第i位的限制进行第i+1位的讨论即可，这样是O(n^3)的，但是我们发现累计计算方案时是一段区间和，我们可以用前缀和优化，这样就变成O(n^2)了,然后用滚动数组优化成了一维的 //递推+前缀和优化,时间复杂度log(n*n) #include<cstdio> #include<iostream> #include<queue> #include<string> #include<cstring> #include<cmath> using namespace std; const int mn=5005,MOD=1000000007; int n,k,l,t; long long dp[mn],f[mn]; //f[i]=1则表示第i项比前一项小，等于2则表示比前一项大 int main() { scanf("%d%d%d",&n,&k,&l); int f1=0;//标志是否有答案 for(int i=1; i<=k; ++i) { scanf("%d",&t); if(f[t+1]!=2) f[t+1]=1; else f1=1; if(f[t+1+1]!=1) f[t+1+1]=2; else f1=1; } for(int i=1; i<=l; ++i) { scanf("%d",&t); if(f[t+1]!=1) f[t+1]=2; else f1=1; if(f[t+1+1]!=2) f[t+1+1]=1; else f1=1; } if(f1) { cout<<0<<endl; return 0; } dp[1]=1;//初始化 for(int i=2; i<=n; ++i) { int sum[mn]= {0}; for(int j=1; j<=i; ++j) sum[j]=(sum[j-1]+dp[j])%MOD; for(int j=1; j<=i; ++j) if(f[i]==1) { dp[j]=sum[j-1]; } else if(f[i]==2) { dp[j]=(sum[i]-sum[j-1]+MOD)%MOD; } else { dp[j]=sum[i]; } } long long ans=0; for(int i=1; i<=n; ++i) ans=(ans+dp[i])%MOD; cout<<ans<<endl; return 0; }