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.


Không có bình luận tại thời điểm này.