wmq的隊(duì)伍

發(fā)布時(shí)間: 2017年4月9日 17:06?? 最后更新: 2017年4月9日 17:07?? 時(shí)間限制: 2000ms?? 內(nèi)存限制: 512M

描述

交大上課需要打卡，于是在上課前的幾分鐘打卡機(jī)前往往會(huì)排起長(zhǎng)隊(duì)。

平時(shí)早睡早起早早打卡的wmq昨晚失眠，今天起晚了，于是他也加入了打卡隊(duì)伍中。

這個(gè)時(shí)候，wmq發(fā)現(xiàn)了神奇的現(xiàn)象，打卡隊(duì)伍可以按人們的身高看成一個(gè)隊(duì)列，左邊是隊(duì)頭，右邊是隊(duì)尾。

對(duì)于隊(duì)列a1...an，wmq想知道其中存在多少的有序k元組l1...lk

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

輸入

輸入有多組數(shù)據(jù)

第一行是一個(gè)正整數(shù)T，1≤T≤15，代表數(shù)據(jù)組數(shù)

每組數(shù)據(jù)第一行是兩個(gè)正整數(shù)n，k，1≤n≤2?104，1≤k≤min(n,100)

n?代表隊(duì)列的人數(shù)，k??的含義見(jiàn)題面

接下來(lái)一行有n個(gè)正整數(shù)，代表1到n的一個(gè)排列，表示隊(duì)伍的身高情況

輸出

對(duì)于每組數(shù)據(jù)，輸出一個(gè)整數(shù)，代表有序k元組的個(gè)數(shù)

考慮到數(shù)字可能很大，將答案對(duì)109+7取模之后輸出

樣例輸入1?復(fù)制 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

很容易想到用動(dòng)態(tài)規(guī)劃的方式來(lái)解決在這道題目，我們用dp[i][j][t]來(lái)表示在前i個(gè)隊(duì)伍里，以t結(jié)尾的j元祖有多少個(gè)

這樣的話轉(zhuǎn)移就是dp[i][j][t] = sum(dp[i-1][j-1][m])其中m > t

但這樣的話空間復(fù)雜度是4*10^10,我們發(fā)現(xiàn)dp[i]只與dp[i-1]有關(guān)，因此可以重復(fù)利用，所以 省掉一維只用dp[j][t]來(lái)表示就好了，這樣的話復(fù)雜度降低到了2*10^6可以忍受了。

另外時(shí)間復(fù)雜度,因?yàn)閕要從1循環(huán)到2*10^4 ，元組長(zhǎng)度 要循環(huán)100次，比t大的m的循環(huán)最差也要循環(huán)2*10^4，因此總的時(shí)間復(fù)雜度為4*10^10顯然不能通過(guò)。

我們要利用這道題目很重要的一點(diǎn)，隊(duì)列中的人是1到n的一個(gè)排列，因此n最大不超過(guò)2*10^4，我們可以想到用樹狀數(shù)組的方法來(lái)求出sum(dp[i-1][j-1][m])的值，只需要logn的復(fù)雜度就行了，注意要為每個(gè)j元組都要開一個(gè)樹狀數(shù)組

int bitree[maxk][maxn];//為j元組開辟樹狀數(shù)組

這樣的話sum(dp[i-1][j-1][m]) 的值實(shí)際上就等于sum(j-1,n) - sum(j-1,t);t是隊(duì)伍中的第i個(gè)元素

注意爆int！別忘記取mod，比賽時(shí)候因?yàn)檫@兩個(gè)低級(jí)錯(cuò)誤WA了6發(fā)。。。。。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的元組個(gè)數(shù) 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; }

創(chuàng)作挑戰(zhàn)賽新人創(chuàng)作獎(jiǎng)勵(lì)來(lái)咯，堅(jiān)持創(chuàng)作打卡瓜分現(xiàn)金大獎(jiǎng)

總結(jié)

以上是生活随笔為你收集整理的dp 树状数组 逆序元组的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

如果覺(jué)得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。