dp 树状数组 逆序元组

wmq的队伍

发布时间: 2017年4月9日 17:06   最后更新: 2017年4月9日 17:07   时间限制: 2000ms   内存限制: 512M

描述

交大上课需要打卡，于是在上课前的几分钟打卡机前往往会排起长队。

平时早睡早起早早打卡的wmq昨晚失眠，今天起晚了，于是他也加入了打卡队伍中。

这个时候，wmq发现了神奇的现象，打卡队伍可以按人们的身高看成一个队列，左边是队头，右边是队尾。

对于队列a1...an，wmq想知道其中存在多少的有序k元组l1...lk

使得1≤l1<l2<...<lk≤n，并且有al1>al2>...>alk

输入

输入有多组数据

第一行是一个正整数T，1≤T≤15，代表数据组数

每组数据第一行是两个正整数n，k，1≤n≤2∗104，1≤k≤min(n,100)

n​代表队列的人数，k​ 的含义见题面

接下来一行有n个正整数，代表1到n的一个排列，表示队伍的身高情况

输出

对于每组数据，输出一个整数，代表有序k元组的个数

考虑到数字可能很大，将答案对109+7取模之后输出

样例输入1 复制 3 2 2 1 2 2 2 2 1 22 3 1 2 3 4 5 16 6 7 8 9 10 19 11 12 14 15 17 18 21 22 20 13 样例输出1 0 1 8

很容易想到用动态规划的方式来解决在这道题目，我们用dp[i][j][t]来表示在前i个队伍里，以t结尾的j元祖有多少个

这样的话转移就是dp[i][j][t] = sum(dp[i-1][j-1][m])其中m > t

但这样的话空间复杂度是4*10^10,我们发现dp[i]只与dp[i-1]有关，因此可以重复利用，所以 省掉一维只用dp[j][t]来表示就好了，这样的话复杂度降低到了2*10^6可以忍受了。

另外时间复杂度,因为i要从1循环到2*10^4 ，元组长度 要循环100次，比t大的m的循环最差也要循环2*10^4，因此总的时间复杂度为4*10^10显然不能通过。

我们要利用这道题目很重要的一点，队列中的人是1到n的一个排列，因此n最大不超过2*10^4，我们可以想到用树状数组的方法来求出sum(dp[i-1][j-1][m])的值，只需要logn的复杂度就行了，注意要为每个j元组都要开一个树状数组

int bitree[maxk][maxn];//为j元组开辟树状数组

这样的话sum(dp[i-1][j-1][m]) 的值实际上就等于sum(j-1,n) - sum(j-1,t);t是队伍中的第i个元素

注意爆int！别忘记取mod，比赛时候因为这两个低级错误WA了6发。。。。。55555

#include <iostream> #include <cstdio> #include <cstring> using namespace std; #define int long long const int maxk = 105; const int maxn = 20005; int bitree[maxk][maxn]; int dp[maxk][maxn];//dp[i][j]表示 i元组，末尾为j的元组个数 const int MOD = 1e9 + 7; int n,k; inline int lowbit(int x){return x&(-x); } void add(int tid,int pos,int val){while(pos <= n){bitree[tid][pos] += val;pos += lowbit(pos);} } int sum(int tid,int pos){int res = 0;while(pos > 0){res += bitree[tid][pos];pos -= lowbit(pos);}return res; } void init(){memset(bitree,0,sizeof(bitree));memset(dp,0,sizeof(dp)); } main(){int T;scanf("%lld",&T);while(T--){init();scanf("%lld%lld",&n,&k);int now;for(int i = 1;i <= n;i++){scanf("%lld",&now);dp[1][now] = 1;add(1,now,1);for(int j = 2;j <= k;j++){dp[j][now] = (sum(j-1,n) - sum(j-1,now))% MOD;add(j,now,dp[j][now]);}}int ans = 0;for(int i = 1;i <= n;i++){ans = (ans + dp[k][i]) % MOD;}printf("%lld\n",ans);}return 0; }

创作挑战赛新人创作奖励来咯，坚持创作打卡瓜分现金大奖

总结

以上是生活随笔为你收集整理的dp 树状数组 逆序元组的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。