PKU 2078 Matrix
http://poj.org/problem?id=2078
行列の行を好きなだけシフトしていい時に、与えられた式の答えを求める。
1行目は変更しなくていいことに気づかなくて、O(n^(n+2))をO(n^(n+1))のオーダーにしないとTLEした。
入力がcinとかだったらまだ間に合わないかもしれない。
多分これは頭悪い方の解法な気がする。
int ret; char c; bool m; int in(){ ret=0; m=0; while(!isdigit(c=getchar()) && c!='-'); if(c=='-')m=1; else ret=c-'0'; while(isdigit(c=getchar()))ret=(ret<<3)+(ret<<1)+c-'0'; if(m)return -ret; return ret; } int mat[10][10]; int ac[7]; int n; int ans; void dfs(int ne){ if(ne==0){ int c=0; rep(i,n){ int sum=0; rep(j,n)sum+=mat[j][(i+ac[j])%n]; c=max(c,sum); } ans=min(c,ans); return; } rep(i,n){ ac[ne-1]=i; dfs(ne-1); } } main(){ while(n=in(),~n){ rep(i,n)rep(j,n)mat[i][j]=in(); ans=1<<28; dfs(n-1); printf("%d\n",ans); } }