首页 > 代码库 > 题解:UESTC1217 The Battle of Chibi
题解:UESTC1217 The Battle of Chibi
题意:对于一个N个数的序列求长度为M的上升子序列总数(结果取%)
1<=N<=1000;1<=M<=N;1<=ai<=109.共1~100组数据,4000MS
解题思路:
考虑使用DP,先写出最朴素形式,DP[i][j][k]表示已判断到第i个数,序列长度为j,前一个数大小为k(已离散化)时方案数。复杂度为O(N*M*N),直接上显然会T
优化方法较为明显,维护n个树状数组S[i],S[j][k]表示到当前为止,最大数小于k且长度为j的序列总数,则每次对S[j](j从min(i,m)到1)进行操作:add(a[i]+1,tmp),其中tmp=ask(j-1,a[i]),则每次转移结束,S[j][k]保存从1到i的所有可能状态,复杂度O(NMlogN)
注意点:S数组转移时循环变量应采用倒序
#include<iostream> #include<cstring> #include<cstdio> #include<cstring> #include<algorithm> using namespace std; const int mo=1000000007; const int maxn=1001; int t,n,m,now,maxs,tmp,ans,gd,wz; int s[2000][maxn+5]; int jl[2000],ys[2000]; int c[2000]; int lowbit(int x){return (x&(-x));} void add(int u,int x,int value){ for (int i=x;i<=maxs+1;i+=lowbit(i)){ s[u][i]=(s[u][i]+value)%mo; } } int ask(int u,int x){ { int sum=0; for (int i=x;i;i-=lowbit(i)) sum=(sum+s[u][i])%mo; return sum; } } bool cmd(int a,int b){ return (jl[a]<jl[b]); } int main(){ freopen("1.in","r",stdin); freopen("1.out1","w",stdout); scanf("%d",&t); for (int q=1;q<=t;++q){ scanf("%d%d",&n,&m);maxs=0; for (int i=1;i<=n;++i) {scanf("%d",&jl[i]);ys[i]=jl[i];} for (int i=1;i<=n;++i) c[i]=i; sort(c+1,c+1+n,cmd); jl[c[1]]=1;wz=0; for (int i=2;i<=n;++i){ if (ys[c[i]]==ys[c[i-1]]) ++wz; jl[c[i]]=i-wz; } maxs=n-wz; memset(s,0,sizeof(s)); add(1,jl[1]+1,1);add(0,1,1); for (int i=2;i<=n;++i){ for (int j=min(i,m);j>=1;--j) if (j>i) break; else { tmp=(ask(j-1,jl[i])) % mo; if (tmp!=0) add(j,jl[i]+1,tmp); } } //cout<<s[0][2]<<endl; int ans=ask(m,maxs+1) % mo; printf("Case #%d: %d\n",q,ans); } return 0; }
题解:UESTC1217 The Battle of Chibi
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。