Hướng dẫn giải của Xếp hàng mua vé

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:longint;
    a,b,f:array[0..60000] of longint;

begin
        read(n);
        for i:=1 to n do read(a[i]);
        for i:=1 to n-1 do read(b[i]);
        f[1]:=a[1];
        for i:=2 to n do
                f[i]:=min(f[i-1]+a[i],f[i-2]+b[i-1]);
        writeln(f[n]);
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[] t = new int[n], f = new int[n+1], r = new int[n-1];
        for( int i = 0; i < n; ++i ) t[i] = scan.nextInt();
        for( int i = 0; i < n-1; ++i ) r[i] = scan.nextInt();
        f[n] = 0; f[n-1] = t[n-1];
        for( int i = n-2; i >= 0; --i )
            f[i] = Math.min(t[i]+f[i+1], r[i]+f[i+2]);
        System.out.println(f[0]);
    }
}

Code mẫu của ladpro98

program nktick;
uses    math;
var     t,r,f:array[1..66666] of longint;
        n:longint;
procedure input;
var     p:text;
        i:longint;
begin
        assign(p,'');
        reset(p);
        readln(p,n);
        for i:=1 to n do read(p,t[i]);
        for i:=1 to n-1 do read(p,r[i]);
        r[n]:=t[n];
        close(p);
end;

procedure dp;
var     i:longint;
begin
        f[n+1]:=0;
        f[n+2]:=0;
        for i:=n downto 1 do
        f[i]:=min(t[i]+f[i+1],r[i]+f[i+2]);
end;

begin
        input;
        dp;
        write(f[1]);
end.

Code mẫu của RR

uses math;
var
  i,n:longint;
  r,t,f:array[1..60111] of longint;
begin
  read(n);
  for i:=1 to n do read(t[i]);
  for i:=1 to n-1 do read(r[i]);

  f[n]:=t[n];
  for i:=n-1 downto 1 do
      f[i]:=min(t[i]+f[i+1],r[i]+f[i+2]);

  writeln(f[1]);
end.

Code mẫu của hieult

#include <stdio.h>
main()
{
int n,t[60000],r[60000],a[60000];
long m=0,f[60000];
scanf("%d",&n);
for(int i=0;i<n;i++)
  scanf("%d",&t[i]);
for(int i=0;i<n-1;i++)
  scanf("%d",&r[i]);
for(int i=0;i<n-1;i++)
  {
  a[i]=t[i]+t[i+1]-r[i];
  if(a[i]<0)
    a[i]=0;
  }
f[0]=0;
f[1]=a[0];
for(int i=2;i<n;i++)
  {
  if(f[i-2]+a[i-1]>f[i-1])
    f[i]=f[i-2]+a[i-1];
  else
    f[i]=f[i-1];
  }
for(int i=0;i<n;i++)
  m+=t[i];
m=m-f[n-1];
printf("%ld ",m);
}

Code mẫu của ll931110

Program NKTICK;
        Const
                input  = '';
                output = '';
        Var
                F,t,r: array[0..60000] of longint;
                    n: longint;

Procedure init;
          Var
                fi: text;
                 i: longint;
          Begin
                Assign(fi, input);
                        Reset(fi);

                        Readln(fi, n);
                        For i:= 1 to n do read(fi, t[i]);
                        For i:= 1 to n - 1 do read(fi, r[i]);
                Close(fi);
          End;

Function min(x,y: longint): longint;
         Begin
                If x < y then min:= x else min:= y;
         End;

Procedure optimize;
          Var
                i: longint;
          Begin
                Fillchar(F, sizeof(F), 0);
                F[1]:= t[1];

                For i:= 2 to n do F[i]:= min(F[i - 2] + r[i - 1],F[i - 1] + t[i]);
          End;

Procedure print;
          Var
                fo: text;
          Begin
                Assign(fo, output);
                        Rewrite(fo);
                        Writeln(fo, F[n]);
                Close(fo);
          End;

Begin
        init;
        optimize;
        print;
End.

Code mẫu của skyvn97

#include<stdio.h>
#define MAX   77777
long t[MAX];
long r[MAX];
long f[MAX];
long g[MAX];
long n;
long min(long x,long y)
{
     if (x<y) return (x); else return (y);     
}
void init(void)
{
     long i;
     scanf("%ld",&n);
     for (i=1;i<=n;i=i+1) scanf("%ld",&t[i]);
     for (i=1;i<n;i=i+1)  scanf("%ld",&r[i]);
}
void optimize(void)
{
     long i;
     f[1]=t[1];
     g[1]=1<<20;
     f[2]=t[1]+t[2];
     g[2]=r[1];
     for (i=3;i<=n;i=i+1)
         {
          f[i]=min(f[i-1],g[i-1])+t[i];
          g[i]=min(f[i-2],g[i-2])+r[i-1];
         }                        
     printf("%ld",min(f[n],g[n]));
}
int main(void)
{
    init();
    optimize();
}

Code mẫu của khuc_tuan

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Main {

    public static void main(String[] args) throws Exception {
        BufferedReader kb = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(kb.readLine());
        StringTokenizer st = new StringTokenizer(kb.readLine());
        int[] t = new int[n];
        for (int i = 0; i < n; ++i)
            t[i] = Integer.parseInt(st.nextToken());
        st = new StringTokenizer(kb.readLine());
        int[] r = new int[n];
        for (int i = 0; i < n - 1; ++i)
            r[i] = Integer.parseInt(st.nextToken());
        int[][] f = new int[n][2];
        int inf = 2000000000;
        f[0][0] = inf;
        f[0][1] = t[0];
        for (int i = 1; i < n; ++i) {
            f[i][0] = f[i - 1][1] + r[i - 1] - t[i - 1];
            f[i][1] = Math.min(f[i - 1][0], f[i - 1][1]) + t[i];
        }
        System.out.println(Math.min(f[n - 1][0], f[n - 1][1]));
    }
}

Bình luận

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

0

HUNG2010 đã bình luận lúc 3, Tháng 12, 2024, 11:22

Đây là một bài rất hay về quy hoạch động, mặc dù đây chỉ là dạng đơn giản nhất của quy hoạch động. Cảm ơn ad đã nghĩ ra bài lập trình này!

4

xthavan đã bình luận lúc 29, Tháng 10, 2024, 7:23

Sự thật là em muốn vào hướng dẫn để đọc giải thuật, gợi ý mà trong hd toàn code mẫu

ducquoc đã bình luận lúc 6, Tháng 1, 2025, 11:00 ← sửa 4 →

Theo tôi đoán thì các bạn ở trên toàn là kỳ cựu, nên nhìn vào đề bài này thấy đơn giản quá (nhìn ra ngay cách giải) + thấy code đã express itself được hệ thức truy hồi rồi. Nên họ cũng ko viết dài thêm.

Tôi là beginner/novice, giờ có tuổi rồi revisit lại kiến thức CTDL&GT 1 chút, xin thử share ý tưởng:

Gọi F là thời gian ngắn nhất để tổng mua vé. (ở đây sẽ dùng 0-index, từ zero)

Khi có 1 người thì: tổng thời gian T[0]. Suy ra F[0] = T[0]

Khi có 2 người xếp hàng thì: tổng thời gian có 2 cách: Một là tự mua từng người (T[1] + T[0]), Hai là người trước mua giùm (R[0]). Suy ra F[1] = min{T[1] + T[0], R[0]}

Khi có 3 người mua hàng thì tương tự: F[2] = min{T[2] + F[1], R[1] + F[0]}. Suy ra tổng quát: F[i] = min{T[i] + F[i-1], R[i-1] + F[i-2]}

Đáp án cuối là F[N-1]. (Ai dùng 1-index như Pascal thì khởi đầu F[1] = T[1], cuối là F[N])

Code mẫu của ducquoc :

https://oj.vnoi.info/src/8084093

import java.io.*; import java.util.*;

//public class Main { public static void main(String[] args) { VoNktick.sol(System.out); } }

@SuppressWarnings({"all"}) // https://oj.vnoi.info/problem/nktick
class VoNktick {
    public static void sol(PrintStream os, InputStream... is) {
        QS in = new QS(is.length > 0 ? is[0] : System.in); PrintWriter out = new PrintWriter(os);
        int N = in.nextInt(), T[] = in.nextIArray(N), R[] = in.nextIArray(N - 1);
        int rs = nktick(T, R, N); // minTimes(T, R, N)
        out.println(rs); out.close(); in.close(); //System.gc();
    }

    static int nktick(int[] T, int[] R, int N) {
        if (N == 1) return T[0];
        int f[] = new int[N]; f[0] = T[0]; f[1] = Math.min(T[0] + T[1], R[0]);
        for (int i = 2; i < N; i++) { f[i] = Math.min(T[i] + f[i - 1], R[i - 1] + f[i - 2]); }
        return f[N - 1];
    }

    final public static void main(String[] args) throws Exception {
        //sol(new PrintStream("O.out"), new FileInputStream("I.inp"));
        sol(System.out, new ByteArrayInputStream("5\n2 5 7 8 4\n4 9 10 10\n".getBytes()));
    }
}
/** delegate quick Scanner */
class QS {
    BufferedReader br; StringTokenizer st;
    public QS(InputStream is) { br = new BufferedReader(new InputStreamReader(new DataInputStream(is)), 4096); }
    public String next() { while (st == null || !st.hasMoreTokens()) { try { st = new StringTokenizer(
            br.readLine()); } catch (IOException e) { e.printStackTrace(); } } return st.nextToken(); }
    public int nextInt() { return Integer.parseInt(next()); }
    public void close() { if (br != null) { try { br.close(); } catch (IOException e) { e.printStackTrace(); } } }
    public int[] nextIArray(int n) { int a[] = new int[n], i = 0; while (i < n) a[i++] = nextInt(); return a; }
}

-DQ

-5
nhat7a đã bình luận lúc 10, Tháng 10, 2024, 12:41
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 = 65000; const int inf = N * 30000; int n, t[N], r[N], F[N][2];

int main() { // freopen("INP.TXT", "r", stdin); // freopen("OUT.TXT", "w", stdout);

scanf("%d", &n); FOR(i,1,n) scanf("%d", &t[i]); FOR(i,1,n-1) scanf("%d", &r[i]); F[1][0] = inf; F[1][1] = t[1]; F[2][0] = r[1]; F[2][1] = t[1] + t[2]; FOR(i,3,n) { F[i][0] = F[i-1][1] - t[i-1] + r[i-1]; F[i][1] = min(F[i-1][0], F[i-1][1]) + t[i]; } printf("%d\n", min(F[n][0], F[n][1])); return 0;

}
Bình luận này đã bị ẩn vì có quá nhiều phản ứng tiêu cực. Nhấn để xem.