题解:UESTC1217 The Battle of Chibi

题意:对于一个N个数的序列求长度为M的上升子序列总数(结果取%)

         1<=N<=1000;1<=M<=N;1<=a_i<=10⁹.共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
#include
#include
#include
#include
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<int ans=ask(m,maxs+1) % mo;printf("Case #%d: %d\n",q,ans);}return 0;
}

转载于:https://www.cnblogs.com/terra/p/6986764.html

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！