/* THE PROGRAM IS MADE BY PYY */
/*----------------------------------------------------------------------------//
Copyright (c) 2012 panyanyany All rights reserved.
URL : http://poj.org/problem?id=1887
Name : 1887 Testing the CATCHER
Classification : 最长非升子序列
Date : Wednesday, July 11, 2012
Time Stage : half an hour
Result:
10420937 panyanyany
1887
Accepted 224K 16MS C++
1692B 2012-07-11 09:59:34
10420935 panyanyany
1887
Accepted 224K 16MS C++
1692B 2012-07-11 09:59:09
10420931 panyanyany
1887
Runtime Error C++
1691B 2012-07-11 09:58:54
10420923 panyanyany
1887
Accepted 340K 0MS C++
1692B 2012-07-11 09:58:22
Test Data :
Review :
数组开到40005,用时0MS,减少到10005的时候,用时却是16MS……郁闷,求解释……
//----------------------------------------------------------------------------*/
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <math.h>
#include <vector>
#include <algorithm>
#include <iostream>
#include <queue>
#include <set>
#include <string>
using namespace std ;
#define MEM(a, v) memset (a, v, sizeof (a)) // a for address, v for value
#define max(x, y) ((x) > (y) ? (x) : (y))
#define min(x, y) ((x) < (y) ? (x) : (y))
#define INF (0x3f3f3f3f)
#define MAXN (1005)
#define L(x) ((x)<<1)
#define R(x) (((x)<<1)|1)
#define M(x, y) (((x)+(y)) >> 1)
#define DB //
int a[MAXN], order[MAXN];
int LNotIncS(int a[], int n)
{
int i, len, r, l, m;
MEM(order, 0);
len = 1;
for (i = 0; i < n; ++i)
{
l = 1;
r = len;
while (l <= r)
{
m = (l + r) >> 1;
if (order[m] >= a[i])
l = m + 1;
else
r = m - 1;
}
if (order[l] < a[i])
order[l] = a[i];
if (len < l)
len = l;
}
return len;
}
int main()
{
int x, n, tc;
n = 0;
tc = 1;
while (scanf("%d", &x))
{
if (0 == n && x == -1)
break;
if (x != -1)
{
a[n++] = x;
}
else
{
if (tc != 1)
putchar('\n');
printf("Test #%d:\n", tc++);
printf(" maximum possible interceptions: %d\n", LNotIncS(a, n));
n = 0;
}
}
return 0;
}
分享到:
相关推荐
Pku acm 第1887题 Testing the CATCHER 代码,有详细的注释,动态规划
北大POJ1163-The Triangle
北大POJ3267-The Cow Lexicon
北大POJ经典结题报告 北大POJ经典结题报告 北大POJ经典结题报告 注重方法,内容详尽,物超所值
北大POJ1027-The Same Game 解题报告+AC代码
北大POJ1426-Find The Multiple【BFS+同余模】 解题报告+AC代码
北大POJ1163-The Triangle 解题报告+AC代码
很多的POJ题目答案!1000~1008,1011~1014,1016,1017,1019,1028,1032,1045,1046,1047,1050,1061,1067,1068,1088,1102,1159,1163,1183,1207,1218,1226,1247,1256,1258,1298,1316,1323,...
poj经典动态规划题目解题报告,包括经典的动态规划题目20多道,可以作为学习动态规划系统的资料,包括题目: Pku acm 1179 Polygon Pku acm 1125 Stockbroker Grapevine Pku acm 1160 post office Pku ...
如果你为在poj上找不到解题思路而痛苦,那么这本书可以为你带来惊喜,里面包括了poj上一部分题解题报告~
ACM POJ 解题报告北大POJ 大量解题代码
北大poj解题报告,希望能帮到软件工程的同学,每天一道,持之以恒,熟能生巧,与您共勉!
北大POJ1159-Palindrome
北大POJ1837-Balance
北大poj JAVA源码
北大POJ第1324题(C++)
北大POJ第1005题答案(C语言)
北大POJ200多道程序解答 完整代码 供大家参考 相互切磋
poj题目分类 简单题 搜索题 模拟题 动态规划 计算几何 递推 数学题 图论 数据结构 贪心 构造 枚举 特殊问题特殊对待 博弈 适合学算法的人进行专项练习