Hướng dẫn giải của Dãy con tăng dài nhất (bản dễ)
Chỉ dùng lời giải này khi không có ý tưởng, và đừng copy-paste code từ lời giải này. Hãy tôn trọng người ra đề và người viết lời giải.
Nộp một lời giải chính thức trước khi tự giải là một hành động có thể bị ban.
Nộp một lời giải chính thức trước khi tự giải là một hành động có thể bị ban.
Lưu ý: Các code mẫu dưới đây chỉ mang tính tham khảo và có thể không AC được bài tập này
Code mẫu của flashmt
uses math; var n,i,j,re:longint; a,f:array[1..1002] of longint; begin read(n); for i:=1 to n do begin read(a[i]); f[i]:=1; for j:=1 to i-1 do if a[i]>a[j] then f[i]:=max(f[i],f[j]+1); re:=max(re,f[i]); end; writeln(re); end.
Code mẫu của happyboy99x
import java.util.Scanner; public class Main { public static void main(String[] args) { Scanner scan = new Scanner(System.in); int n = scan.nextInt(); int[] a = new int[n+1], f = new int[n+1]; for( int i = 0; i < n; ++i ) { a[i] = scan.nextInt(); } a[n++] = 100000; for( int i = 0; i < n; ++i ) { f[i] = 1; for( int j = 0; j < i; ++j ) { if (a[j] < a[i]) { f[i] = Math.max(f[i], f[j]+1); } } } System.out.println(f[n-1]-1); } }
Code mẫu của ladpro98
program daycontang; const fi = ''; fo = ''; var mang,f: array[0..30001] of longint; i,t,n:longint; inp,oup:text; function find(i,j,x:longint):longint; var l,r,m,k:longint; begin l:=i;r:=j; while l<=r do begin m:=(l+r) div 2; if mang[f[m]]<mang[x] then begin k:=m; l:=m+1; end else r:=m-1; end; exit(k); end; procedure input; begin assign(inp,fi); reset(inp); readln(inp,n); for i:=1 to n do read(inp,mang[i]); close(inp); end; procedure output; begin assign(oup,fo); rewrite(oup); write(oup,t); close(oup); end; begin input; f[1]:=1; t:=1; for i:=2 to n do begin if mang[i]<mang[f[1]] then f[1]:=i else if mang[i]>mang[f[t]] then begin inc(t); f[t]:=i; end else begin f[find(1,t,i)+1]:=i; end; end; output; end.
Code mẫu của RR
import sys n = input() a = map(int, sys.stdin.readline().split()) res = 0 l = len(a) f = [1] * l for i in range(0,l): for j in range(0,i): if a[j] < a[i]: f[i] = max(f[i], f[j] + 1) res = max(res, f[i]) print res
Code mẫu của hieult
#include <stdio.h> main() { int n,a[1000],f[1000],max,m=0; scanf("%d",&n); for(int i=0;i<n;i++) scanf("%d",&a[i]); f[0]=1; for(int i=1;i<n;i++) { max=0; for(int j=0;j<i;j++) if(a[i]>a[j]&&max<f[j]) max=f[j]; f[i]=max+1; } for(int i=0;i<n;i++) if(f[i]>m) m=f[i]; printf("%d",m); }
Code mẫu của ll931110
Program LIQ; Const input = ''; output = ''; max = 1000; Var x,l: array[0..max + 1] of integer; n: integer; Procedure enter; Var f: text; i: integer; Begin Assign(f, input); Reset(f); Readln(f, n); For i:= 1 to n do read(f, x[i]); Close(f); x[0]:= Low(integer); x[max + 1]:= High(integer); End; Procedure optimize; Var i,j,jmax: integer; Begin l[n + 1]:= 1; For i:= n downto 0 do Begin jmax:= n + 1; For j:= i + 1 to n + 1 do If (x[j] > x[i]) and (l[j] > l[jmax]) then jmax:= j; l[i]:= l[jmax] + 1; End; End; Procedure printresult; Var f: text; Begin Assign(f, output); Rewrite(f); Writeln(f, l[0] - 2); Close(f); End; Begin enter; optimize; printresult; End.
Code mẫu của skyvn97
#include<stdio.h> using namespace std; const int maxn = 3e4 + 4; long int n, a [maxn], lis [maxn], t [maxn], p; int main (void) { scanf ("%d", &n); a [0] = -1e9; a [n + 1] = 1e9; for (int i = 1; i <= n + 1; ++i) { if (i <= n) scanf ("%ld", &a [i]); int l = 0, r = p; while (l < r) { int m = (l + r + 1) / 2; if (a [t [m]] < a [i]) l = m; else r = m - 1; } lis [i] = l + 1; if (lis [i] > p) t [++p] = i; else if (a [i] < a [t [lis [i]]]) t [lis [i]] = i; } printf ("%ld\n", lis [n + 1] - 1); return 0; }
Code mẫu của khuc_tuan
n = input() a = [int(x) for x in raw_input().split()] f = [] r = 0 for i in range(n): t = 1 for j in range(len(f)): if a[j]<a[i]: t= max(f[j]+1,t) f.append(t) r = max(t,r) print r
Bình luận
Để post code trong comment, thì đặt đoạn code giữa cặp "three backtick quote" của Markdown ``` . VD: Java code
Để ẩn thì dùng "spoiler" prefix của VNOI (
>!
) ở đầu dòng. VD:-Duc,
include <bits/stdc++.h>
using namespace std;
typedef long long ll; typedef pair<int,int> ii; typedef unsigned long long ull;
define X first
define Y second
define pb push_back
define mp make_pair
define ep emplace_back
define EL printf("\n")
define sz(A) (int) A.size()
define FOR(i,l,r) for (int i=l;i<=r;i++)
define FOD(i,r,l) for (int i=r;i>=l;i--)
define fillchar(a,x) memset(a, x, sizeof (a))
define faster iosbase::syncwith_stdio(false); cin.tie(NULL); cout.tie(NULL);
const int N = 1005; int n, a[N], F[N];
int main() { // freopen("INP.TXT", "r", stdin); // freopen("OUT.TXT", "w", stdout);
}