The Battle of Chibi
发布时间:2020-12-14 04:45:28 所属栏目:大数据 来源:网络整理
导读:The Battle of Chibi 给出一段长度为n的序列 ({a_i}) ,求其中长度为m的严格上升子序列个数 (mod 10^9+7) , (nleq 10^3) 。 解 不难想到设 (f[i][j]) 表示以第i个位置结尾,长度为j的LSIS,因此我们有 [f[i][j]=sum_{k=1,a_ia_k}^{i-1}f[k][j-
The Battle of Chibi 给出一段长度为n的序列({a_i}),求其中长度为m的严格上升子序列个数(mod 10^9+7),(nleq 10^3)。 解不难想到设(f[i][j])表示以第i个位置结尾,长度为j的LSIS,因此我们有 [f[i][j]=sum_{k=1,a_i>a_k}^{i-1}f[k][j-1]] 边界:(f[i][1]=1,i=1,2,...,n),其余为0 答案:(sum_{i=1}^nf[i][m]) 注意到这是(O(n^3))算法,优先考虑转移优化,问题实际上是要寻找前面(a_k)小于(a_i)的f前缀和,考虑给a排序,也就是给a离散化,在离散化的数组里面建立前缀和数据结构(如线段树,树状数组),每次在对应的位置上查询修改前缀和,于是可以优化为(O(n^2log^n)) 参考代码: #include <iostream> #include <cstdio> #include <cstring> #include <algorithm> #define il inline #define ri register #define yyb 1000000007 using namespace std; struct Map{ int a[1001],b[1001],n; il void prepare(int m,int ar[]){ n=m; for(ri int i(1);i<=n;++i) a[i]=ar[i];sort(a+1,a+n+1); for(ri int i(1);i<=n;++i)b[i]=dfs(ar[i]); } il int look(int x){ return b[x]; } il int dfs(int x){ int l(1),mid,r(n); while(l<=r){ mid=l+r>>1; if(x>a[mid])l=mid+1; else r=mid-1; }return l; } }L; struct lowbit{ int n,a[1001]; il void prepare(int m){ n=m,memset(a,sizeof(a)); } il void change(int p,int v){ while(p<=n)(a[p]+=v)%=yyb,p+=-p&p; } il int ask(int p){ int ans(0); while(p)(ans+=a[p])%=yyb,p-=-p&p;return ans; } }ar; int a[1001],dp[1001][1001]; il void read(int&),work(); int main(){ int lsy,i;read(lsy); for(i=1;i<=lsy;++i)printf("Case #%d: ",i),work(); return 0; } il void work(){ int n,m;read(n),read(m); for(int i(1);i<=n;++i)read(a[i]); L.prepare(n,a),memset(dp,sizeof(dp)); for(int i(1);i<=n;++i)dp[i][1]=1; for(int i,j(2);j<=m;++j){ ar.prepare(n); for(i=1;i<=n;++i) dp[i][j]=ar.ask(L.look(i)-1),ar.change(L.look(i),dp[i][j-1]); }int ans(0); for(int i(1);i<=n;++i)(ans+=dp[i][m])%=yyb; printf("%dn",ans); } il void read(int &x){ x&=0;ri char c;while(c=getchar(),c<'0'||c>'9'); while(c>='0'&&c<='9')x=(x<<1)+(x<<3)+(c^48),c=getchar(); } (编辑:李大同) 【声明】本站内容均来自网络,其相关言论仅代表作者个人观点,不代表本站立场。若无意侵犯到您的权利,请及时与联系站长删除相关内容! |