@OceanEye7年前
07/13
14:46
神奇树状数组优化DP+组合数
思路很暴力……但是就是比较难连起来
第一步：
dp[i][j]表示枚举到第i位结尾且以第i位为结尾时 不下降子序列长度为j的情况数量
\( dp[i][j]=\sum_{k=1}^{j}(dp[i-1][k]) \)
第二步：
令 g[x] 表示所有长度为x的 不下降子序列 的数量
\( g[x]=\sum_{k=1}^{n}dp[k][x] \)
可以发现我们的ans和这个g[x]是由联系的
长度为x的 不下降子序列 的数量……和两个东西有关系
第一类—->从g[x+1]直接减少一位过来 第二类—->从非g[x+1]的过来 【参照定义理解】
第二类的数量是要记入答案的数量的
就稍微的暴力用n阶乘来做就好了，反正n不大
\( ans=\sum_{k=1}^{n}g[k]*(n-k)!-g[k+1]*g[k+1]*(n-k-1)!*(k+1) \)
以下代码
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 |
#include <cstdio> #include <algorithm> #include <cstring> #include <iostream> #include <cstdlib> #include <cmath> #define ll long long #define INF 1000000000 #define For(i,a,b) for(int i=a;i<=b;++i) #define p(x) ('0'<=x&&x<='9') char cc; int C; template <class T> void read( T &x ) { x=0; C=1; cc=getchar(); while(!p(cc)) { if(cc=='-') C=-1; cc=getchar(); } while(p(cc)) { x=x*10+cc-48; cc=getchar(); } x*=C; } #undef p using namespace std; #define N 2010 #define mod 1000000007LL #define lb(x) (x&-x) ll sum[N][N]; void add(int y,int pos,int val) { for(;pos<=N;pos+=lb(pos)) sum[y][pos]+=val,sum[y][pos]%=mod; } int query(int y,int pos) { static ll ret; for(ret=0;pos;pos-=lb(pos)) ret+=sum[y][pos]; return (int)(ret%mod); } #undef lb int dp[N][N],a[N],c[N],n; ll g[N],ans,l[N]; void init() { read(n); For(i,1,n) read(a[i]),c[i]=a[i]; sort(c+1,c+1+n); For(i,1,n) a[i]=lower_bound(c+1,c+1+n,a[i])-c; for(int i=1;i<=n;i++) { for(int j=i;j>=2;--j) { dp[i][j]=query(j-1,a[i]); add(j,a[i],dp[i][j]); } dp[i][1]=1; add(1,a[i],1); } } int main() { init(); For(i,1,n) for(int j=1;j<=n;j++) g[i]+=dp[j][i],g[i]%=mod; l[0]=1; ans+=g[n]; for(int i=n-1;i;i--) { l[n-i]=l[n-i-1]*(n-i)%mod; ans+=g[i]*l[n-i]%mod-(g[i+1]*l[n-i-1])%mod*(i+1)%mod; ans%=mod; } printf("%lld\n",(ans+mod)%mod); return 0; } |