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.
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