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;
}

Download