首页 > 代码库 > CodeChef Little Elephant and Movies [DP 排列]
CodeChef Little Elephant and Movies [DP 排列]
https://www.codechef.com/FEB14/problems/LEMOVIE
题意：
对于一个序列，定义其“激动值”为序列中严格大于前面所有数的元素的个数。
给定n个数p1;,p2... pn，求这n个数的所有排列中，激动值不超过k的个数。$1 k \le n \le 200，1 \le pi \le 200$
这种题有一个很神的想法：
把排列按某种顺序往里插入，使得后不会影响前
对于本题，先离散化去重后，从大到小插入，后插入的元素不会影响已经插入的元素严格大于前面所有数
$f[i][j]$表示插入了前$i$大的数，激动值为$j$的方案数
激动值改变只有可能是当前要插入的数中有一个放在了最前面
转移时分类讨论有没有数插在最前面，需要用到隔板法，
设已经插入$x$个数，第$i$大的有$y$个数
$f(i,j)=f(i-1,j)*\binom{x+y-1}{x-1}*{y!}\ +\ f(i-1,j-1)*\binom{x+y-1}{x}*{y!}$
#include <iostream>#include <cstdio>#include <cstring>#include <algorithm>using namespace std;typedef long long ll;const int N=205,INF=1e9+5,P=1e9+7;inline int read(){ char c=getchar();int x=0,f=1; while(c<‘0‘||c>‘9‘){if(c==‘-‘)f=-1;c=getchar();} while(c>=‘0‘&&c<=‘9‘){x=x*10+c-‘0‘;c=getchar();} return x*f;}int n,k,a[N];int m,d[N],s[N];inline bool cmp(int a,int b){return a>b;}ll c[N][N],fac[N];inline void mod(ll &x){if(x>=P) x-=P;}void ini(){ c[0][0]=1;fac[0]=1; for(int i=1;i<=200;i++){ c[i][0]=1; for(int j=1;j<=i;j++) mod(c[i][j]+=c[i-1][j]+c[i-1][j-1]); fac[i]=fac[i-1]*i%P; }}ll f[N][N];void dp(){ f[0][0]=1; for(int i=1;i<=m;i++) for(int j=1;j<=k;j++){ int x=s[i-1],y=d[i]; f[i][j]=f[i-1][j]*c[x+y-1][x-1]%P*fac[y]%P; mod(f[i][j]+=f[i-1][j-1]*c[x+y-1][x]%P*fac[y]%P); //printf("f %d %d %lld\n",i,j,f[i][j]); } ll ans=0; for(int i=1;i<=k;i++) mod(ans+=f[m][i]); printf("%lld\n",ans);}int main(){ freopen("in","r",stdin); ini(); int T=read(); while(T--){ memset(d,0,sizeof(d)); n=read();k=read(); for(int i=1;i<=n;i++) a[i]=read(); sort(a+1,a+1+n,cmp); m=0; d[++m]=1; for(int i=2;i<=n;i++){ if(a[i]==a[i-1]) d[m]++; else d[++m]=1; } for(int i=1;i<=m;i++) s[i]=s[i-1]+d[i]; //for(int i=1;i<=m;i++) printf("%d ",d[i]);puts(""); //for(int i=1;i<=m;i++) printf("%d ",s[i]);puts(""); dp(); }}
CodeChef Little Elephant and Movies [DP 排列]
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。