SPOJ.com - Problem LIS

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ó)

Hiện tại, bài tập này đã có trên online judge chính thức của VNOI, bạn có thể truy cập ở đây: https://oj.vnoi.info/problem/lis

(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

Submit solution!

Đượ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

Giải bài trực tuyến

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

Input

Output

Example