首页 > 代码库 > zoj4991

zoj4991

2024-07-21 18:40:28   217人阅读

这题说的是给了一个序列长度为n 然后求这个序列的严格递增序列长度是m的方案有多少种，如果用dp做那么对于状态有dp[n][m]=dp[10000][100]，时间复杂度为n*m*n接受不了那么想想是否可以再这个上加些什么样的优化。树状数组 对于每个值离散在树状数组中然后对于每个点都有以他为结尾点的递增序列的长度为1..100，那么他的状态是怎么来的呢？当他的i长度的是等于在他前面比他来的小的 长度为i-1的的种数，然后得到了这个值将他在加进这第i棵树状数组中然后就得到解了，不断地进行这个过程时间n*m*log2(n);

#include <iostream>#include <cstdio>#include <string.h>#include <algorithm>using namespace std;typedef int ll;const int MAX_N = 10005;const ll MOD = 123456789;ll C[105][MAX_N];ll A[MAX_N],B[MAX_N];int len;int lowbit(int x){  return x&(-x);}void add(int x,ll value, int floor){     while(x<=len){        C[floor][x]=(C[floor][x]+value)%MOD;        x+=lowbit(x);     }}ll sum(int x, int floor){    ll ans=0;    while(x>0){         ans=(ans+C[floor][x])%MOD;         x-=lowbit(x);    }    return ans; }int main(){     int n,m;    while(scanf("%d%d",&n,&m)==2){         for(int i=0; i<n; ++i){             scanf("%d",&A[i]);             B[i] = A[i];         }         sort( B , B + n );         len = unique(B,B+n)-B;         memset(C,0,sizeof(C));         for(int i =0; i<n; ++i){             int loc = lower_bound(B,B+len,A[i])-B+1;             add(loc,1,1);             for(int j = 2; j<=m ; ++j ){                ll num = sum(loc-1,j-1);                add(loc,num,j);             }         }         ll ans = sum(len,m);         printf("%d\n",ans);     }     return 0;}
View Code

 

zoj4991


联系
我们