HDU5542 – The Battle of Chibi(DP+树状数组优化)

HDU5542

【题意】给出N(<=1000)长的序列，求出M长度的上升子序列的数量。

【分析】首先，容易想到N^3的DP，dp[i][j]表示以a[i]结尾长度为j的子序列的数量。

那么转移方程为: dp[i][j] = sum{dp[k][j-1]} (1 <= k < i && a[i] > a[k]),初始话长度为1时dp值为1。

但是N^3必然超时，所以想到优化，观察sum{dp[k][j-1]}其实就是对于每个i之前所有值小于a[i]时候的总和，这个可以用树状数组维护，那么再给每个长度建一颗树状数组即可，这样复杂度O(N^2 * log(N))。

【N^3暴力DP超时代码】

#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
#define rep(i,a,n) for(int i = a; i < n; i++)
#define repe(i,a,n) for(int i = a; i <= n; i++)
#define per(i,n,a) for(int i = n; i >= a; i--)
#define clc(a,b) memset(a,b,sizeof(a))
const int INF = 0x3f3f3f3f, MAXN = 1000+10, MOD = 1000000007;
int dp[MAXN][MAXN],a[MAXN];

int main()
{
#ifdef SHY
	freopen("d:\\1.txt", "r", stdin);
#endif
	int t,count = 0;
	scanf("%d", &t);
	while(t--)
	{
		int n,m;
		scanf("%d%d", &n,&m);
		repe(i,1,n) scanf("%d", &a[i]);
		a[n+1] = 0;
		clc(dp,0);
		repe(i,1,n)
		{
			repe(j,1,m)
			{
				if(j == 1) dp[i][j] = 1;
				else
				{
					rep(k,0,i)
					{
						if(a[k] < a[i])
							dp[i][j] = (dp[i][j]+dp[k][j-1])%MOD;
					}
				}
			}
		}
		int ans = 0;
		repe(i,1,n) ans = (ans+dp[i][m])%MOD;
		printf("Case #%d: %d\n", ++count,ans);
	}
	return 0;
}

【AC CODE】2698ms

#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
#define rep(i,a,n) for(int i = a; i < n; i++)
#define repe(i,a,n) for(int i = a; i <= n; i++)
#define per(i,n,a) for(int i = n; i >= a; i--)
#define clc(a,b) memset(a,b,sizeof(a))
const int INF = 0x3f3f3f3f, MAXN = 1000+10, MOD = 1000000007;
int dp[MAXN][MAXN],a[MAXN],sot[MAXN],mx;

struct Tree{
	int cnt[MAXN];
	void init()
	{
		clc(cnt,0);
	}
	int lowbit(int x){return x&-x;}
	void add(int x, int v)
	{
		while(x <= mx)
		{
			cnt[x] = (cnt[x]+v)%MOD;
			x += lowbit(x);
		}
	}
	int query(int x)
	{
		int ans = 0;
		while(x > 0)
		{
			ans = (ans+cnt[x])%MOD;
			x -= lowbit(x);
		}
		return ans;
	}
}tree[MAXN];

int main()
{
#ifdef SHY
	freopen("d:\\1.txt", "r", stdin);
#endif
	int t,count = 0;
	scanf("%d", &t);
	while(t--)
	{
		int n,m;
		scanf("%d%d", &n,&m);
		repe(i,1,n) scanf("%d", &a[i]),sot[i] = a[i];
		sort(sot+1,sot+1+n);
		mx = unique(sot+1,sot+1+n)-sot-1;
		repe(i,1,n) a[i] = lower_bound(sot+1,sot+1+mx,a[i])-sot,tree[i].init();
		clc(dp,0);
		repe(i,1,n)
		{
			repe(j,1,m)
			{
				if(j == 1) dp[i][j] = 1;
				else dp[i][j] = tree[j-1].query(a[i]-1);
				tree[j].add(a[i],dp[i][j]);
			}
		}
		int ans = 0;
		repe(i,1,n) ans = (ans+dp[i][m])%MOD;
		printf("Case #%d: %d\n", ++count,ans);
	}
	return 0;
}