DISNEY2 - Công viên Disneyland (version 2)
Tác giả: skyvn97
Ngôn ngữ: C++
#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;
}