1109: [POI2007]堆积木Klo
Time Limit: 10 Sec Memory Limit: 162 MB
Submit: 948 Solved: 341
[Submit][Status][Discuss]
Description
Mary在她的生日礼物中有一些积木。那些积木都是相同大小的立方体。每个积木上面都有一个数。Mary用他的
所有积木垒了一个高塔。妈妈告诉Mary游戏的目的是建一个塔,使得最多的积木在正确的位置。一个上面写有数i
的积木的正确位置是这个塔从下往上数第i个位置。Mary决定从现有的高塔中移走一些,使得有最多的积木在正确
的位置。请你告诉Mary她应该移走哪些积木。
Input
第一行为一个数n,表示高塔的初始高度。第二行包含n个数a1,a2,...,an,表示从下到上每个积木上面的数。
(1<=n<=100000,1<=ai<=1000000)。
Output
注意:请输出最多有多少点可以处在正确位置
Sample Input
5
1 1 2 5 4
1 1 2 5 4
Sample Output
3
HINT
Source
分析
OTZ Neighthorn
一开始是三维——
i > j && a[i] > a[j] && a[i] - i <= a[j] - j
然后,巨机的Neighthorn告诉我们,这其实是二维,因为满足后两个条件时,第一维一定满足。
所以是二维了——
a[i] > a[j] && a[i] - i <= a[j] - j
然而蒟蒻的我依然不会,于是巨机的Neighthorn有开始指点迷津。
说,如果你把a[i]看作新的下标,这就是个水水的最长不严格上升子序列问题。
∑( 口 ||, 再次 OTZ Neighthorn。
代码
#include <cstdio>
#include <cstring>
#include <algorithm> #define lim 10000000 class Scanner
{
private:
char *c; public:
Scanner(void)
{
c = new char[lim];
fread(c, , lim, stdin);
} int nextInt(void)
{
int res = ;
bool neg = ; while (*c < '')
if (*c++ == '-')
neg ^= true; while (*c >= '')
res = res* + *c++ - ''; return neg ? -res : res;
}
}in; #define N 1000005 int n, a[N]; struct pair
{
int x, y;
pair(void) {};
pair(int a, int b) :
x(a), y(b) {};
}; pair p[N]; int cmp(const void *a, const void *b)
{
if (((pair *)a)->x != ((pair *)b)->x)
return ((pair *)a)->x - ((pair *)b)->x;
else return -((pair *)a)->y + ((pair *)b)->y;
} int tmp[N]; #define inf 0x3f3f3f3f
#define low lower_bound
#define upp upper_bound signed main(void)
{
n = in.nextInt(); for (int i = ; i <= n; ++i)
a[i] = in.nextInt(); for (int i = ; i <= n; ++i)if (a[i] <= i)
p[i] = pair(a[i], i - a[i]);
else p[i] = pair(inf, inf); qsort(p + , n, sizeof(pair), cmp); using namespace std; memset(tmp, inf, sizeof(tmp)); for (int i = ; i <= n; ++i)
{
int t = p[i].y;
*upp(tmp, tmp + i, t) = t;
} printf("%d\n", low(tmp, tmp + n, inf) - tmp);
}
BZOJ_1109.cpp
@Author: YouSiki