首页 > 代码库 > BZOJ1109 [POI2007]堆积木Klo
BZOJ1109 [POI2007]堆积木Klo
第一眼看出是动态规划。
然后写方程：令f[i]表示下面i个积木里面必须取第i个的情况下满足要求的最多个数。
则f[i] = max(f[j] + 1)
其中j满足以下三个条件
(1) j < i
(2) a[j] < a[i]
(3) a[i] - a[j] <= i - j
把(3)变形：a[i] - i <= a[j] - j ......(4)
这时ZYH神犇告诉我(2) + (3)可以推出(1)，即只需满足(2)、(4)两个条件即可
于是得到方法了：先排序(第一关键字a[i] - i升序，第二关键字a[i]降序)，然后直接求新数列的LIS即可。
其实这里求LIS时，每次要求[1, i]的最大值，不需要线段树维护，只要树状数组就可以了。
1 /************************************************************** 2 Problem: 1109 3 User: rausen 4 Language: C++ 5 Result: Accepted 6 Time:332 ms 7 Memory:3148 kb 8 ****************************************************************/ 9 10 #include <cstdio>11 #include <cmath>12 #include <algorithm>13 14 using namespace std;15 16 struct Rec{17 int num, x;18 } a[150000];19 int ans, n, f[150000], Bit[150000];20 21 bool cmp(Rec a, Rec b){22 return a.x == b.x ? a.num < b.num : a.x > b.x;23 } 24 25 inline int lowbit(int x){26 return x & (-x);27 }28 29 int query(int x){30 if (!x) return 0;31 int res = 0;32 while (x){33 res = max(res, Bit[x]);34 x -= lowbit(x);35 }36 return res;37 }38 39 void add(int x, int y){40 while (x <= n){41 Bit[x] = max(Bit[x], y);42 x += lowbit(x);43 }44 }45 46 int main(){47 scanf("%d", &n);48 for (int i = 1; i <= n; ++i){49 scanf("%d", &a[i].num);50 a[i].x = a[i].num - i;51 }52 sort(a + 1, a + n + 1, cmp);53 54 for (int i = 1; i <= n; ++i){55 if (a[i].x > 0) continue;56 int X = query(a[i].num - 1);57 f[i] = X + 1;58 ans = max(ans, f[i]);59 add(a[i].num, f[i]);60 } 61 printf("%d\n", ans);62 return 0;63 }
BZOJ1109 [POI2007]堆积木Klo
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。