Gửi bài giải
Điểm:
1,00 (OI)
Giới hạn thời gian:
1.0s
Giới hạn bộ nhớ:
256M
Tác giả:
Dạng bài
Ngôn ngữ cho phép
C, C#, C++, Go, Java, Pascal, Perl, PHP, Python, Ruby, Rust, Scratch, Swift
Cho một dãy số nguyên gồm ~N~ phần tử ~a_1, a_2, …, a_N~. Một dãy con đơn điệu tăng của dãy trên là dãy ~a_{i_1}, a_{i_2}, …, a_{i_k}~ sao cho: ~i_1 < i_2 < … < i_k~ và ~a_{i_1} < a_{i_2} < … < a_{i_k}~. Hãy cho biết dãy con đơn điệu tăng của dãy đã cho có nhiều nhất bao nhiêu số hạng?
Input
- Dòng đầu chứa số nguyên dương ~N~;
- Dòng thứ hai chứa ~N~ số nguyên dương ~a_1, a_2, …, a_N~, mỗi số cách nhau bởi một dấu cách.
Giới hạn:
- ~1 ≤ n ≤ 1000, -10^9 ≤ a_i ≤ 10^9~
Output
- Ghi ra độ dài của dãy con đơn điệu tăng dài nhất.
Sample
Input #1
6
1 2 5 4 6 2
Output #1
4
Hint
Giải thích #1:
- Dãy con tăng dài nhất là dãy ~1, 2, 4, 6~ độ dài dãy này là ~4~.
Problem source: Chuyên Sơn La Online Judge
Bình luận
include <bits/stdc++.h>
Code full AC nhé mọi người, cái này là dùng quy hoạch động, độ phức tạp của code này là O(n^2) nhưng vì đây là bản dễ nên vẫn AC.
include<bits/stdc++.h>
using namespace std; using ll=long long; // int main(){ int n; ll a[1001]; cin>>n; vector<int> l(n,1); for(int i=0;i<n;i++) cin>>a[i]; for(int i=0;i<n;i++){ for(int j=0;j<i;j++){ if(a[i]>a[j]){ l[i]=max(l[i],l[j]+1); } } } cout<<*max_element(l.begin(),l.end())<<endl;; return 0; }
include <bits/stdc++.h>
using namespace std;
void sol(long long a[], long long n){ int l[100000]={1}; for(int i=0; i<n; i++){ for(int j=0; j<i; j++){ if(a[i] > a[j]){ l[i] = max( l[i], l[j]+1 ); } } } int MAX = INTMIN; for(int i = 0; i<n; i++){ if(l[i]>MAX){ MAX = l[i]; } } cout<<MAX; } int main(){ iosbase::syncwithstdio(false); cin.tie(NULL); long long a[100002]; long long n; cin>>n; for(int i=0; i<n; i++){ cin>>a[i]; } sol(a,n); return 0; }
day so: 1 2 5 4 5 6 Vi tri: 0 1 2 3 4 5 day so khi sort: 1 2 4 5 5 6 Vi tri khi sort: 0 1 3 2 4 5 taa thay khi sort a[i1]<a[i2] nhung vi tri lai nguoc lai vi vay ta se dem xoi
https://luyencode.net/src/441116
Đầu tiên nhập vào một số
n
.Khi nào
n > 0
.Thì nhập vào
1
sốa
.Tiếp theo dùng hàm
lower_bound()
để tìmm
là vị trí phần tử đầu tiên trong multiset có giá trị lớn hơn hoặc bằng vớia
Sau khi dùng hàm
lower_bound()
xong các bạn phải cộng thêm1
vì vị trím
trong multiset thực tế làm+1
.Rồi kiểm tra xem nều
m != multiset.end()
thì xoám
đi.(Nếu như
m != multiset.end()
thì xoá đi để tìm1
vị trí khác thoả mãn)Thì kích thước của multiset sẽ là kết quả của bài.
Code mẫu (C++) tại Đây
Code Juan nha mn
Hỗ trợ mọi người nhaa!!!
include <bits/stdc++.h>
using namespace std;
int main(){ ios::syncwithstdio(false); cin.tie(nullptr); int n; cin >> n ; int a[n]; for(int i=0;i<n;i++){ cin >> a[i]; } vector<int> v(n,1); for(int i=0;i<n;i++){ for(int j=0;j<i;j++){ if(a[i]>a[j]){ v[i] = max(v[i],v[j]+1); } } } cout << *max_element(v.begin(),v.end()); }
Bài này dùng quy hoạch động nhá
code:
-Na.yn-
test 6 la jz mng;-;??
include <iostream>
using namespace std; int main(){ int n; long long a[1000]; long long b[1000]; cin >> n; for(int i = 1;i<=n;i++){ cin >>a[i]; }
Ủa em chạy thử 1 vài case ngoài mà k biết lỗi ở đâu luôn á:') Mn giúp em với ạ
ví dụ 5 1 7 3 4 8 thì chuỗi con dài nhất phải là 4(1,3,4,8), mà code của bạn ra 3(1,7,8)