Editorial for Nối mạng


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

var n,i:integer;
    a:array[0..25000] of longint;
    t:longint;

begin
     readln(n);
     readln(a[0]); a[1]:=a[0];
     for i:=2 to n-1 do
     begin
          readln(t);
          if a[i-1]>a[i-2] then a[i]:=a[i-2]+t
          else a[i]:=a[i-1]+t;
     end;
     write(a[n-1]);
end.

Code mẫu của happyboy99x

#include <algorithm>
#include <bitset>
#include <cctype>
#include <cfloat>
#include <climits>
#include <cmath>
#include <complex>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <ctime>
#include <deque>
#include <functional>
#include <list>
#include <map>
#include <numeric>
#include <queue>
#include <set>
#include <stack>
#include <string>
#include <utility>
#include <vector>
using namespace std;

typedef pair<int, int> ii;
typedef vector<ii> vii;
typedef vector<vii> vvii;
typedef vector<int> vi;
typedef vector<vi> vvi;

#define sz(a) int((a).size())
#define fi first
#define se second
#define pb push_back
#define mp make_pair
#define all(c) (c).begin(), (c).end()
#define tr(c,i) for(typeof((c).begin()) i = (c).begin(), _e = (c).end(); it != _e; ++it)
#define present(c,x) ((c).find(x) != (c).end())
#define cpresent(c,x) (find(all(c),x) != (c).end())
#define rep(i,n) for(int i = 0, _n = (n); i < _n; ++i)
#define repd(i,n) for(int i = (n)-1; i >= 0; --i )
#define fo(i,a,b) for(int i = (a), _b = (b); i <= _b; ++i)
#define fod(i,a,b) for(int i = (a), _b = (b); i >= _b; --i)

#define INF 1000000000
#define N 25005

int d[N], f[N];

int main() {
    //freopen( "input.txt", "r", stdin );
    //freopen( "output.txt", "w", stdout );
    int n; scanf( "%d", &n );
    for( int i = 1; i < n; ++i ) scanf( "%d", d+i ); d[n] = INF;
    f[0] = 0; f[1] = d[1];
    fo(i,2,n) f[i] = min(f[i-2]+d[i-1], f[i-1]+d[i]);
    printf( "%d\n", f[n] );
    return 0;
}

Code mẫu của ladpro98

program nkcable;
uses    math;
const   maxN = 25555;
        fi='';
var     a,f:array[1..maxN] 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-1 do
        readln(inp,a[i]);
        close(inp);
end;

procedure init;
begin
        f[1]:=a[1];
        f[2]:=a[1]+a[2];

end;

procedure dp;
var     i:longint;
begin
        for i:=3 to n-1 do
        f[i]:=min(f[i-1],f[i-2])+a[i];
end;

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

Code mẫu của RR

uses math;
var
  n,i:longint;
  a,f:array[1..50000] of longint;
begin
  read(n);
  for i:=2 to n do
    read(a[i]);
  f[2]:=a[2];
  f[3]:=a[2]+a[3];
  for i:=4 to n do
      f[i]:=min(f[i-1]+a[i],f[i-2]+a[i]);
  writeln(f[n]);
end.

Code mẫu của hieult

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

Code mẫu của ll931110

Program NKCABLE;
        Const
                input  = '';
                output = '';
        Var
                L,F: array[0..25000] 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 - 1 do readln(fi, L[i]);
                Close(fi);
          End;

Procedure optimize;
          Var
                i: longint;
          Begin
                F[0]:= 0;
                F[1]:= 1000000000;

                For i:= 2 to n do
                        Begin
                                If F[i - 1] > F[i - 2] then F[i]:= F[i - 2]
                                                       else F[i]:= F[i - 1];
                                F[i]:= F[i] + L[i - 1];
                        End;
          End;

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

Begin
        init;
        optimize;
        printresult;
End.

Code mẫu của skyvn97

#include<stdio.h>
#define MAX   30000
long opt[MAX];
long dis[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);
     dis[1]=0;
     for (i=2;i<=n;i=i+1)
         {
          scanf("%ld",&dis[i]);
          dis[i]=dis[i]+dis[i-1];
         }
}
void optimize(void)
{
     long i;
     opt[1]=0;
     opt[2]=dis[2];
     opt[3]=dis[3];
     for (i=4;i<=n;i=i+1)
         opt[i]=min(opt[i-1],opt[i-2])+dis[i]-dis[i-1];
     printf("%ld",opt[n]);
}
int main(void)
{
    //freopen("CABLE.INP","r",stdin);
    //freopen("CABLE.OUT","w",stdout);
    init();
    optimize();
}

Code mẫu của khuc_tuan

import java.io.BufferedReader;
import java.io.InputStreamReader;

public class Main {

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

Comments

Please read the guidelines before commenting.


There are no comments at the moment.