C. Subsequences(樹狀數組優化的dp)

記錄一下,雖然挺好想的,但是樹狀數組優化

d

p

dp

dp還是第一次

普

通

轉

移

應

該

都

知

道

,

是

n

2

k

的

大

暴

力

普通轉移應該都知道,是n^2k的大暴力

普通轉移應該都知道,是n2k的大暴力

for(int i=1;i<=n;i++)
for(int j=1;j<i;j++)
{
	if(a[i]<=a[j] )	continue;
	for(int q=1;q<=k;q++)
		dp[i][q]+=dp[j][q-1];
}	
           

每

次

去

[

1

i

−

]

找

對

象

太

耗

時

間

了

每次去[1,i-1]找轉移對象太耗時間了

每次去[1,i−1]找轉移對象太耗時間了

我

們

不

就

需

要

那

些

比

a

小

答

案

嗎

我們不就是需要那些比a[i]小的答案嗎

我們不就是需要那些比a[i]小的答案嗎

/*
1 2 3 4 5
找到遞增的長k+1的子序列個數 
dp[i][len]表示以i結尾長len的方案 
*/
#include <bits/stdc++.h>
using namespace std;
#define int long long
const int maxn=1e5+10;
int n,k,a[maxn],dp[maxn][12];
class like_tree_array
{
	private:
		int sumn[maxn];
		int lowbit(int x){
			return x&(-x);
		}
	public:
		void add(int x,int k){
			for(;x<=n;x+=lowbit(x))	sumn[x]+=k;
		}
		int ask(int x){
			int ans=0;
			for(;x;x-=lowbit(x))	ans+=sumn[x];
			return ans;
		}
}mp[12];
signed main()
{
	cin >> n >> k;
	for(int i=1;i<=n;i++)	cin >> a[i];
	for(int i=1;i<=n;i++)
	for(int j=k+1;j>=1;j--)//倒序枚舉,因為下面有插入操作,類似01背包 
	{
		if( j==1 )	dp[i][j]=1;
		else dp[i][j]=mp[j-1].ask( a[i] );//小于a[i]的都行 
		mp[j].add( a[i],dp[i][j] );
	}
	int ans=0;
	for(int i=k+1;i<=n;i++)	ans+=dp[i][k+1];
	cout << ans;
}