2078:Matrix

keyword

行列　BruteForce　C++

概要

n*n(n<=7)の行列が与えられる。各行を好きなだけrotateできる。このとき各列の和の最大値を最小化する問題。
サイズが小さいので全探索する。それなりに高速化する必要があるが、対称性から1列目は固定する、実際に回転はしない、和の計算を全てのパターンに対してn^2でしない、などすればよい。

static int mat[7][7];
static int lst[7];
int n;

int dfs(int y){
    if(y==n) return *max_element(lst,lst+n);
    int ret = 1<<30, i, rot=0;
    REP(rot,n){
        REP(i,n) lst[i] += mat[y][(i+rot)%n];
        ret = min(dfs(y+1), ret);
        REP(i,n) lst[i] -= mat[y][(i+rot)%n];
    }
    return ret;
}

int main(){
    int i, j;
    while(n = readint(), n+1){
        REP(i,n)REP(j,n){
            mat[i][j] = readint();
        }
        REP(i,n) lst[i] = mat[0][i];
        printf("%d\n",dfs(1));
    }
    return 0;
}