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.

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

Hãy đọc nội quy trước khi bình luận.



  • 0
    nhat7a  đã bình luận lúc 6, Tháng 3, 2024, 14:16

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

    cin >> n;
    FOR(i,1,n) scanf("%d", &a[i]);
    
    a[++n] = 10001;
    FOR(j,1,n) {
        F[j] = 1;
        FOR(i,1,j-1) if (a[i] < a[j]) F[j] = max(F[j], F[i]+1);
    }
    
    cout << F[n]-1;
    
    return 0;
    

    }