首页 > 代码库 > 【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 动态规划+树状数组
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。