Editorial for VOI 09 Bài 1 - Trò chơi với băng số


Remember to use this editorial only when stuck, and not to copy-paste code from it. Please be respectful to the problem author and editorialist.
Submitting an official solution before solving the problem yourself is a bannable offence.

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;
    x,y,s,z:int64;

begin
      read(n);
      x:=-1000000; y:=0;
      for i:=1 to n do
      begin
           read(s);
           z:=y;
           y:=max(y,x-s);
           x:=max(x,z+s);
      end;
      writeln(max(x,y));
end.

Code mẫu của happyboy99x

#include <cstdio>

int main() {
    long long s; int d, t, n;
    scanf( "%d%d", &n, &t ); s = t;
    for( int i = 1; i < n; ++i ) {
        scanf( "%d", &d );
        if ( d > t ) s += d-t;
        t = d;
    }
    printf( "%lld\n", s );
    return 0;
}

Code mẫu của ladpro98

program linegame;
uses    math;

const   le=1;
        chan=2;
        fi='';
var     f:array[le..chan,0..1000001] of int64;
        a:array[0..1000001] of longint;

        n:longint;


procedure input;
var     inp:text;
        i:longint;
begin
        assign(inp,fi);
        reset(inp);
        readln(inp,n);
        for i:=1 to n do
        read(inp,a[i]);
        close(inp);
end;

procedure dp;
var     i,j:longint;
begin
        for j:=1 to n do
        for i:=le to chan do
        begin
                if i=le then
                f[i,j]:=max(f[chan,j-1]+a[j],f[le,j-1])
                else
                f[i,j]:=max(f[le,j-1]-a[j],f[chan,j-1]);
        end;
end;

begin
        input;
        dp;
        write(max(f[chan,n],f[le,n]));
end.

Code mẫu của RR

uses math;
var
  i,n:longint;
  a,f1,f2:array[1..1000111] of int64;

begin
  read(n);
  for i:=1 to n do read(a[i]);
  f1[1]:=a[1];
  f1[2]:=max(f1[1],a[2]);
  f2[2]:=max(a[1]-a[2],0);

  for i:=3 to n do
    begin
      f1[i]:=max(f2[i-1]+a[i],f1[i-1]);
      f2[i]:=max(f1[i-1]-a[i],f2[i-1]);
    end;

  writeln(max(f1[n],f2[n]));
end.

Code mẫu của hieult

#include <stdio.h>
//#include <conio.h>
main()
{
long long n,a,b,A;
scanf("%lld",&n);
scanf("%lld",&a);
A=a;
for(long i=2;i<=n;i++)
{
  scanf("%lld",&b);
  if(b>a)
    A=A+b-a;
  a=b;
}
printf("%lld",A); 
//getch();
}

Code mẫu của ll931110

Program LINEGAME;
        Const
                input  = '';
                output = '';
        Var
                    a: array[1..1000000] of integer;
                F,non: array[1..2,1..1000000] of int64;
                    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, a[i]);

                Close(fi);
          End;

Function max(x,y: int64): int64;
         Begin
                If x < y then max:= y else max:= x;
         End;

Procedure optimize;
          Var
                i: longint;
          Begin
                F[1,1]:= a[1];          F[2,1]:= 0;
                non[1,1]:= 0;           non[2,1]:= 0;

                For i:= 2 to n do
                        Begin
                                F[1,i]:= max(F[2,i - 1],non[2,i - 1]) + a[i];
                                F[2,i]:= max(F[1,i - 1],non[1,i - 1]) - a[i];

                                non[1,i]:= max(F[1,i - 1],non[1,i - 1]);
                                non[2,i]:= max(F[2,i - 1],non[2,i - 1]);
                        End;
          End;

Procedure solve;
          Var
                  fo: text;
                 k,p: int64;
          Begin
                  Assign(fo, output);
                        Rewrite(fo);

                  k:= max(F[1,n],F[2,n]);
                  p:= max(non[1,n],non[2,n]);

                  If k > p then writeln(fo, k) else writeln(fo, p);
                  Close(fo);
          End;

Begin
        init;
        optimize;
        solve;
End.

Code mẫu của skyvn97

#include<cstdio>
#include<iostream>
#define MAX   1000100
#define FOR(i,a,b) for (int i=(a);i<=(b);i=i+1)
#define REP(i,n) for (int i=0;i<(n);i=i+1)
using namespace std;
typedef long long ll;
int a[MAX];
int n;
ll f[MAX][2];
template<class T>
    void maximize(T &x,const T &y) {
        if (x<y) x=y;
    }
void init(void) {
    scanf("%d",&n);
    FOR(i,1,n) scanf("%d",&a[i]);
}
void optimize(void) {
    f[1][1]=a[1];
    f[1][0]=0LL;
    FOR(i,1,n-1) REP(j,2) {
        maximize(f[i+1][j],f[i][j]);
        maximize(f[i+1][1-j],f[i][j]+(j<1)*a[i+1]-(j>0)*a[i+1]);
    }
    cout << max(f[n][0],f[n][1]);
}
int main(void) {
    init();
    optimize();
    return 0;
}

Code mẫu của khuc_tuan

#include <iostream>
using namespace std;

int main() {
    long long m1 = 0, m2 = 0;
    int n, x;
    scanf("%d", &n);
    for(int i=0;i<n;++i) {
        scanf("%d", &x);
        long long new_m1 = max(m1, m2 - x);
        long long new_m2 = max(m2, m1 + x);
        m1 = new_m1;
        m2 = new_m2;
    }
    printf("%lld\n", max(m1,m2));
    return 0;   
}

Comments

Please read the guidelines before commenting.


There are no comments at the moment.