Problem hidden
|This problem was hidden by Editorial Board member probably because it has incorrect language|version or invalid test data, or description of the problem is not clear.|

LIS - Dãy con tăng dài nhất (bản khó)




(Giống bài LIQ) Cho một dãy gồm N số nguyên (1 ≤ N ≤ 30000). Hãy tìm dãy con tăng dài nhất trong dãy đó. In ra số lượng phần tử của dãy con. Các số trong phạm vi longint.

Input

  • Dòng đầu tiên gồm số nguyên N.
  • Dòng thứ hai gồm N số mô tả dãy.

Output

Gồm một số nguyên duy nhất là đáp số của bài toán

Example

Input:
5
2 1 4 3 5

Output:
3

Được gửi lên bởi:nha.duong
Ngày:2007-09-15
Thời gian chạy:1s
Giới hạn mã nguồn:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Ngôn ngữ cho phép:Tất cả ngoại trừ: ERL GOSU JS-RHINO NODEJS PERL6 PYPY RUST SED VB.NET
Nguồn bài:Bài cổ điển

hide comments
2019-10-29 12:24:12
em mới học lập trình cho em hỏi AC là gì vậy
2019-06-21 16:41:02
lỗi znec là lỗi j ạ mọi người thông não hộ em phát
2019-06-05 07:03:33
mới học BIT gõ code phê quá :)) BIT gắt vl :))
2019-05-21 19:15:47
1 đấm ac với chặt nhị phân

Last edit: 2019-05-21 19:16:45
2019-03-31 09:34:11
code AC: https://bit.ly/2TQdmyY
2019-03-18 18:39:02
Tại sao cùng code mà biên dịch bằng C++4.3.2 bị lỗi truy cập SIGSEGV. CPP14 lại accept :( ai biết giải thích hộ mình với. Mất bao nhiêu tg để debug :(
2018-10-28 08:51:19
Bit nhớ nén không hỏng =)))
CYB
2018-08-31 11:28:40
dãy con đơn điệu tăng mà cứ tưởng ko giảm, chỉ vì 1 dấu bằng mà tốn mấy đấm mới AC đc :))
2018-06-21 03:28:03
Trau cung AC:
#include <bits/stdc++.h>
typedef long long ll;
typedef unsigned long long ull;
#define forinc(a,b,c) for(int a=b,_c=c;a<=_c;++a)
#define fordec(a,b,c) for(int a=b,_c=c;a>=_c;--a)
using namespace std;
int f[30001];
long long a[30001];
void read(long long & x)
{
x=0;
char c=getchar();
while(c<'0'||c>'9') c=getchar();
while('0'<=c&&c<='9')
{
x=x*10+c-'0';
c=getchar();
}
}
int main()
{
int n;
cin>>n;
forinc(i,1,n) {read(a[i]);f[i]=1;}
forinc(i,2,n)
{
fordec(j,i-1,max(1,i-1000)) if(a[i]>a[j]) f[i]=max(f[i],f[j]+1);
}
int kq=1;
forinc(i,1,n) kq=max(kq,f[i]);
cout<<kq;
}

2018-04-21 18:48:00
Solution chi tiết: https://bit.ly/2F3aes1
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.