首页 > 代码库 > 【bzoj1109】[POI2007]堆积木Klo 动态规划+树状数组

【bzoj1109】[POI2007]堆积木Klo 动态规划+树状数组

题目描述

Mary在她的生日礼物中有一些积木。那些积木都是相同大小的立方体。每个积木上面都有一个数。Mary用他的所有积木垒了一个高塔。妈妈告诉Mary游戏的目的是建一个塔,使得最多的积木在正确的位置。一个上面写有数i的积木的正确位置是这个塔从下往上数第i个位置。Mary决定从现有的高塔中移走一些,使得有最多的积木在正确的位置。请你告诉Mary她应该移走哪些积木。

输入

第一行为一个数n,表示高塔的初始高度。第二行包含n个数a1,a2,...,an,表示从下到上每个积木上面的数。

输出

注意:请输出最多有多少点可以处在正确位置

样例输入

5
1 1 2 5 4

样例输出

3


题解

动态规划+树状数组

设f[i]表示在前i个积木中选择i最多有多少点处在正确位置。

那么如果j能够更新i,需要满足条件:$j<i\ \&\&\ a_j<a_i\ \&\&\ a_i-a_j\le i-j(j-a_j\le i-a_i)$。

这看似是三个条件的三维偏序问题,而实际上由后两个条件可以推出第一个条件,可以忽略,就变成了二维偏序问题。

那么就可以按照a值从小到大排序,就变为了最长不下降子序列问题。可以用树状数组来维护。

注意:由于要求$a_j$要严格小于$a_i$,所以当它们相等时不应进行更新。这里为了避免这个问题,将$a_i$相等的i按照$i-a_i$从大到小排序,防止多余的更新。

#include <cstdio>#include <cstring>#include <algorithm>#define N 100010using namespace std;struct data{	int x , y;}a[N];int v[N] , tot , f[N] , dp[N] , n;bool cmp1(data a , data b){	return a.y < b.y;}bool cmp2(data a , data b){	return a.x == b.x ? a.y > b.y : a.x < b.x;}void update(int x , int a){	int i;	for(i = x ; i <= tot ; i += i & -i) f[i] = max(f[i] , a);}int query(int x){	int i , ans = 0x80000000;	for(i = x ; i ; i -= i & -i) ans = max(ans , f[i]);	return ans;}int main(){	int i , ans = 0;	scanf("%d" , &n) , n ++ , a[1].y = 1;	for(i = 2 ; i <= n ; i ++ ) scanf("%d" , &a[i].x) , a[i].y = i - a[i].x;	sort(a + 1 , a + n + 1 , cmp1) , v[0] = 0x80000000;	for(i = 1 ; i <= n ; i ++ )	{		if(a[i].y != v[tot]) v[++tot] = a[i].y;		a[i].y = tot;	}	sort(a + 1 , a + n + 1 , cmp2);	memset(f , 0x80 , sizeof(f)) , update(a[1].y , 0);	for(i = 2 ; i <= n ; i ++ ) dp[i] = query(a[i].y) + 1 , update(a[i].y , dp[i]) , ans = max(ans , dp[i]);	printf("%d\n" , ans);	return 0;}

 

 

【bzoj1109】[POI2007]堆积木Klo 动态规划+树状数组