Hướng dẫn giải của Công viên Disneyland (version 2)


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;
const fi='';
      maxn=210;
      oo=10000000;
var n,re:longint;
    a,f:array[0..maxn,0..maxn] of longint;

procedure rf;
var i,j:longint;
begin
     read(n);
     for i:=1 to n do
         for j:=1 to n do
             read(a[i,j]);
end;

procedure pr;
var i,j,x:longint;
begin
     for i:=0 to n do
         for j:=0 to n do
             f[i,j]:=oo;
     f[1,1]:=0;
     for i:=1 to n-1 do
         for j:=1 to n-1 do
         begin
              x:=max(i,j)+1;
              f[i,x]:=min(f[i,x],f[i,j]+a[j,x]);
              f[x,i]:=f[i,x];
              f[j,x]:=min(f[j,x],f[i,j]+a[i,x]);
              f[x,j]:=f[j,x];
         end;
     re:=oo;
     for i:=1 to n do
         re:=min(re,f[i,n]+a[n,1]+a[i,1]);
     writeln(re);
end;

begin
     assign(input,fi); reset(input);
     rf;
     pr;
     close(input);
end.

Code mẫu của happyboy99x

#include<algorithm>
#include<iostream>
#include<cstring>
using namespace std;

const int N = 200, INF = 1e9;
int d[N][N], f[N][N], n;

template<class T> void checkMin(T &a, const T &b) {
    if(b < a) a = b;
}

int main() {
    ios::sync_with_stdio(false);
    cin >> n;
    for(int i = 0; i < n; ++i)
        for(int j = 0; j < n; ++j)
            cin >> d[i][j];
    memset(f, 0x3f, sizeof f);
    int res = INF;
    f[0][0] = 0;
    for(int i = 0; i < n; ++i)
        for(int j = 0; j < n; ++j) if(f[i][j] < INF) {
            int next = max(i, j) + 1;
            if(next == n) checkMin(res, f[i][j] + d[i][0] + d[j][0]);
            else {
                checkMin(f[i][next], f[i][j] + d[j][next]);
                checkMin(f[next][j], f[i][j] + d[i][next]);
            }
        }
    cout << res << endl;
    return 0;
}

Code mẫu của ladpro98

#include <bits/stdc++.h>
const int N = 222;
const int oo = 1000000009;
using namespace std;
int a[N][N], F[N][N], n;
int main()
{
    //freopen("DISNEY1.in", "r", stdin);
    scanf("%d\n", &n);
    int i, j, k;
    for(i=1; i<=n; i++)
        for(j=1; j<=n; j++)
            scanf("%d", &a[i][j]);
    n++;
    for(j=1; j<=n; j++)
        a[n][j] = a[j][n] = a[1][j];
    for(i=1; i<=n; i++)
        for(j=1; j<=n; j++)
            F[i][j] = oo;
    F[1][1] = 0;
    for(i=1; i<=n; i++)
    for(j=1; j<=n; j++) {
        k = max(i, j) + 1;
        F[k][j] = min(F[k][j], F[i][j] + a[i][k]);
        F[i][k] = min(F[i][k], F[i][j] + a[j][k]);
        if (k == n)
        F[k][k] = min(F[k][k], F[i][j] + a[i][k] + a[j][k]);
    }
    printf("%d", F[n][n]);
    return 0;
}

Code mẫu của RR

program DISNEY2;
const
  FINP='';
  FOUT='';
  MAXN=202;
  oo= maxlongint div 2;
var
  d,c:array[1..MAXN,1..MAXN] of longint;
  n:integer;
procedure inp;
var
  f:text;
  i,j:integer;
begin
  assign(f,FINP); reset(f);
  readln(f,n);
  for i:=1 to n do
    for j:=1 to n do
      read(f,c[i,j]);
  close(f);
  for i:=2 to n do
    c[i,n+1]:=c[1,i];
end;
procedure ans;
var
  f:text;i,j:longint;
begin
  assign(f,FOUT); rewrite(f);
  writeln(f,d[n+1,n+1]);
  close(f);
end;
function min(a,b:longint):longint;
begin
  if a<b then min:=a else min:=b;
end;
procedure solve;
var
  i,j:integer;
begin
  for i:=1 to n+1 do
    for j:=1 to n+1 do
      d[i,j]:=oo;
  d[1,1]:=0;
  d[2,1]:=c[1,2];
  d[1,2]:=c[1,2];
  for i:=3 to n+1 do
    begin
      for j:=1 to i-2 do d[i,j]:=d[i-1,j]+c[i-1,i];
      for j:=1 to i-2 do
        d[i,i-1]:=min(d[i,i-1],d[i-1,j]+c[j,i]);
    end;
  for i:=1 to n do
    d[n+1,n+1]:=min(d[n+1,n+1],d[n+1,i]+d[i,n+1]);
  for i:=1 to n-1 do
    d[n+1,n+1]:=min(d[n+1,n+1],d[n,i]+c[n,n+1]+c[i,n+1]);
end;
begin
  inp;
  solve;
  ans;
end.

Code mẫu của hieult

#include <stdio.h>
//#include <conio.h>
#define  oo 10000000;

int n;
int BestConfig,F[202][202],a[202][202];

void Enter()
{
    int i,j;
    scanf("%d",&n);
    for( i=1;i<=n;i++)
        for( j=1;j<=n;j++)
        {
        scanf("%d",&a[i][j]);
        F[i][j]= oo;
        }
}

int min(int a,int b)
{
    if(a<b) return a;
    else return b;
}

void Optimize()
{
    int i,j,k;
    F[2][1] = a[1][2];
    F[1][2] = a[1][2];
    F[2][2] = 2*a[1][2];
    for(i=2;i<=n;i++)
        for(j=1;j<=i;j++)
        {
                F[i+1][j] = min(F[i+1][j],F[i][j]+a[i][i+1]);
                F[j][i+1] = F[i+1][j];
                F[i][i+1] = min(F[i][i+1],F[i][j]+a[j][i+1]);
                F[i+1][i] = F[i][i+1];
        }
}
void PrintResult()
{
    int i;
    BestConfig = oo;
    for(i=1;i<=n;i++)
        if( BestConfig>F[n][i]+a[n][1]+a[i][1])
            BestConfig = F[n][i]+a[n][1]+a[i][1];
    printf("%d",BestConfig);
}
int main()
{
    //freopen("DISNEY1.in","r",stdin);
    Enter();
    if(n==1) printf("0");
    else
    {             
            Optimize();
            PrintResult();
    }
   // getch();
}

Code mẫu của ll931110

//#pragma comment(linker, "/STACK:16777216")
#include <algorithm>
#include <bitset>
#include <cmath>
#include <ctime>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <deque>
#include <fstream>
#include <functional>
#include <iostream>
#include <map>
#include <set>
#include <sstream>
#include <stack>
#include <queue>
#include <vector>
#include <utility>
using namespace std;

int n,L[205][205],f[205][205];

int main()
{
//    freopen("disney2.in","r",stdin);
//    freopen("disney2.ou","w",stdout);
    scanf("%d", &n);
    for (int i = 1; i <= n; i++)
      for (int j = 1; j <= n; j++) scanf("%d", &L[i][j]);
    for (int i = 1; i <= n; i++)
      for (int j = 1; j <= n; j++) f[i][j] = 1 << 29;
    f[1][1] = 0;  f[1][2] = L[1][2];
    for (int j = 2; j <= n; j++)
      for (int i = 1; i < j; i++)
      {
            f[i][j + 1] = min(f[i][j + 1],f[i][j] + L[j][j + 1]);
            f[j][j + 1] = min(f[j][j + 1],f[i][j] + L[i][j + 1]);
        }
    int ret = 1 << 29;
    for (int i = 1; i <= n; i++) ret = min(ret,f[i][n] + L[i][1] + L[n][1]);
    printf("%d\n", ret);
}

Code mẫu của skyvn97

#include<cstdio>
#include<cstring>
#define MAX   211
#define FOR(i,a,b) for (int i=(a);i<=(b);i=i+1)
#define minimize(x,y) if(x>y) x=y
const int INF=(int)1e6+7;
int a[MAX][MAX];
int f[MAX][MAX];
int n;
int max(int x,int y) {
    if (x>y) return (x); else return (y);
}
void init(void) {
    scanf("%d",&n);
    FOR(i,1,n) FOR(j,1,n) scanf("%d",&a[i][j]);
    FOR(i,1,n) {
        a[i][n+1]=a[i][1];
        a[n+1][i]=a[1][i];
    }
    memset(f,-1,sizeof f);
}
int dp(int x,int y) {
    if (x>n) return (a[y][n+1]);
    if (y>n) return (a[x][n+1]);
    if (f[x][y]>=0) return (f[x][y]);
    int &res=f[x][y];
    res=INF;
    int z=max(x,y)+1;
    minimize(res,dp(z,y)+a[x][z]);
    minimize(res,dp(x,z)+a[y][z]);
    return (res);
}
void process(void) {
    printf("%d\n",dp(1,1));
}
int main(void) {
    init();
    process();
    return 0;
}

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.