HDU5542 BIT优化dp-白红宇

HDU5542 BIT优化dp

阅读量：4881 次

发布时间：2019-06-11

本文共 2699 字，大约阅读时间需要 8 分钟。

http://acm.hdu.edu.cn/showproblem.php?pid=5542

题意：求严格递增的长度为M的序列的组数。

当dp的优化方案不那么容易一眼看出来的时候，我们可以考虑先写一个朴素算法，在朴素算法的基础上去考虑优化。

正如这题，很显然用dp[i][j]存储长度为i的序列以j结尾的情况。

然后有两种方法去递推。

一种是从1--M序列的长度，对于每一个数字去寻找他前面比她小的数列进行递推，递推方程dp[i][j] += dp[i - 1][k]; (k < j && a[k] < a[j])

第二种方法是从1--N枚举每个数，对于每个数直接寻找他前面的所有满足上面k条件的数字进行递推。

两种方法时间复杂度相同，朴素算法都是T * M * N * N，显然会TLE，但是考虑在其中一层，也就是寻找他前面枚举条件的数这一步进行优化，当我们用树状数组维护前缀的和的时候，我们就可以把一层N优化变为lnN，总的时间复杂度变成O(TNMln(N));

For(i,1,M){            Mem(tree,0);            if(i == 1) add(1,1);            For(j,1,N){                dp[i & 1][j] = getsum(a[j] - 1) % mod;                 add(a[j],dp[i + 1 & 1][j]);            }        }

第一种方法的主要优化代码

For(i,1,N){    For(j,1,M){        if(j == 1) dp[j & 1][i] = 1;        else dp[j & 1][i] = getsum(j - 1,a[i] - 1) % mod;        add(j,a[i],dp[j & 1][i]);    }}

第二种方法的主要优化代码

#include #include 
      
       #include 
       
        #include 
        
         #include 
         
          #include 
          
           #include 
           
            #include 
            
             #include 
             
              #include 
              
               #include 
               
                #include 
                
                 #include 
                 
                  #include 
                  
                   #include 
                   
                    using namespace std;#define For(i, x, y) for(int i=x;i<=y;i++) #define _For(i, x, y) for(int i=x;i>=y;i--)#define Mem(f, x) memset(f,x,sizeof(f)) #define Sca(x) scanf("%d", &x)#define Sca2(x,y) scanf("%d%d",&x,&y)#define Scl(x) scanf("%lld",&x); #define Pri(x) printf("%d\n", x)#define Prl(x) printf("%lld\n",x); #define CLR(u) for(int i=0;i<=N;i++)u[i].clear();#define LL long long#define ULL unsigned long long #define mp make_pair#define PII pair
                    
                     #define PIL pair
                     
                      #define PLL pair
                      
                       #define pb push_back#define fi first#define se second typedef vector
                       
                         VI;const double eps = 1e-9;const int maxn = 1010;const LL INF = 1e18;const int mod = 1e9 + 7; int N,M,tmp,K; LL a[maxn];int cnt;LL Hash[maxn];inline LL read(){ LL now=0;register char c=getchar(); for(;!isdigit(c);c=getchar()); for(;isdigit(c);now=now*10+c-'0',c=getchar()); return now;}LL dp[2][maxn];LL tree[maxn];void add(int x,LL t){ for(;x <= cnt + 1; x += x & -x) tree[x] = (tree[x] + t) % mod;}LL getsum(int x){ LL s = 0; for(;x > 0;x -= x & -x) s = (s + tree[x]) % mod; return s;}int main(){ int T; Sca(T); int CASE = 1; while(T--){ Sca2(N,M); For(i,1,N) Hash[i] = a[i] = read(); sort(Hash + 1,Hash + 1 + N); cnt = unique(Hash + 1,Hash + 1 + N) - Hash - 1; For(i,1,N) a[i] = lower_bound(Hash + 1,Hash + 1 + cnt,a[i]) - Hash + 1; Mem(dp,0); For(i,1,M){ Mem(tree,0); if(i == 1) add(1,1); For(j,1,N){ dp[i & 1][j] = getsum(a[j] - 1) % mod; add(a[j],dp[i + 1 & 1][j]); } } LL ans = 0; For(i,0,N) ans = (ans + dp[M & 1][i]) % mod; printf("Case #%d: ",CASE++); Prl(ans); } #ifdef VSCode system("pause"); #endif return 0;}

转载于:https://www.cnblogs.com/Hugh-Locke/p/9637298.html

你可能感兴趣的文章