HDU5542 BIT优化dp

时间：2023-03-08 21:10:37

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,,M){

            Mem(tree,);

            if(i == ) add(,);

            For(j,,N){

                dp[i & ][j] = getsum(a[j] - ) % mod;

                add(a[j],dp[i +  & ][j]);

            }

        }

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

    For(i,,N){

    For(j,,M){

        if(j == ) dp[j & ][i] = ;

        else dp[j & ][i] = getsum(j - ,a[i] - ) % mod;

        add(j,a[i],dp[j & ][i]);

    }

}

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

#include <map>

#include <set>

#include <ctime>

#include <cmath>

#include <queue>

#include <stack>

#include <vector>

#include <string>

#include <cstdio>

#include <cstdlib>

#include <cstring>

#include <sstream>

#include <iostream>

#include <algorithm>

#include <functional>

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<int,int>

#define PIL pair<int,long long>

#define PLL pair<long long,long long>

#define pb push_back

#define fi first

#define se second

typedef vector<int> VI;

const double eps = 1e-;

const int maxn = ;

const LL INF = 1e18;

const int mod = 1e9 + ;

int N,M,tmp,K;

LL a[maxn];

int cnt;

LL Hash[maxn];

inline LL read()

{

   LL now=;register char c=getchar();

   for(;!isdigit(c);c=getchar());

   for(;isdigit(c);now=now*+c-'',c=getchar());

   return now;

}

LL dp[][maxn];

LL tree[maxn];

void add(int x,LL t){

    for(;x <= cnt + ; x += x & -x) tree[x] = (tree[x] + t) % mod;

}

LL getsum(int x){

    LL s = ;

    for(;x > ;x -= x & -x) s = (s + tree[x]) % mod;

    return s;

}

int main()

{

    int T; Sca(T);

    int CASE = ;

    while(T--){

        Sca2(N,M);

        For(i,,N)    Hash[i] = a[i] = read();

        sort(Hash + ,Hash +  + N);

        cnt = unique(Hash + ,Hash +  + N) - Hash - ;

        For(i,,N) a[i] = lower_bound(Hash + ,Hash +  + cnt,a[i]) - Hash + ;

        Mem(dp,);

        For(i,,M){

            Mem(tree,);

            if(i == ) add(,);

            For(j,,N){

                dp[i & ][j] = getsum(a[j] - ) % mod;

                add(a[j],dp[i +  & ][j]);

            }

        }

        LL ans = ;

        For(i,,N) ans = (ans + dp[M & ][i]) % mod;

        printf("Case #%d: ",CASE++);

        Prl(ans);

    }

    #ifdef VSCode

    system("pause");

    #endif

    return ;

}

相关文章