ZOJ2418 Matrix 2017-04-18 21:05 73人阅读 评论(0) 收藏

Matrix


Time Limit: 2 Seconds      Memory Limit: 65536 KB

Given an n*n matrix A, whose entries Ai,j are integer numbers ( 0 <= i < n, 0 <= j < n ). An operation SHIFT at row i ( 0 <= i < n ) will move the integers in the row one position
right, and the rightmost integer will wrap around to the leftmost column.

ZOJ2418 Matrix                                                                                            2017-04-18 21:05             73人阅读              评论(0)              收藏

You can do the SHIFT operation at arbitrary row, and as many times as you like. Your task is to minimize

ZOJ2418 Matrix                                                                                            2017-04-18 21:05             73人阅读              评论(0)              收藏

Input

The input consists of several test cases. The first line of each test case contains an integer n. Each of the following n lines contains n integers, indicating the matrix A. The input
is terminated by a single line with an integer -1. You may assume that 1 <= n <= 7 and |Ai,j| < 104.

Output

For each test case, print a line containing the minimum value of the maximum of column sums.

Sample Input

2

4 6

3 7

3

1 2 3

4 5 6

7 8 9

-1

Sample Output

11

15


Source: Asia 2004, Shanghai (Mainland China), Preliminary

————————————————————————————————————

题目的意思是每一行可以任意移动求每列和的最大值的最小值

暴力DFS枚举行与行之间关系,可以开一个数组A保存每一行第一个数位置效率n^(n-1),求最小n^2 ,总共n^(n+1)

#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm>
#include <queue>
#include <set>
#include <stack>
#include <map>
#include <functional>
#include <bitset>
#include <string> using namespace std; #define LL long long
#define INF 0x3f3f3f3f int a[10][10];
int ans[10];
int n,mn; void dfs(int x)
{
if(x==n)
{
int mx=-1;
for(int i=0; i<n; i++)
{
int ans1=0;
for(int j=0; j<n; j++)
{
int pos=ans[j]+i;
if(pos>=n) pos-=n;
ans1+=a[j][pos];
}
mx=max(ans1,mx); }
mn=min(mn,mx);
return;
}
for(int i=0; i<n; i++)
{
ans[x]=i;
dfs(x+1);
}
} int main()
{
while(~scanf("%d",&n))
{
if(n==-1)
break;
for(int i=0; i<n; i++)
for(int j=0; j<n; j++)
scanf("%d",&a[i][j]);
mn=INF;
ans[0]=0;
dfs(1);
printf("%d\n",mn);
} return 0;
}
上一篇:poj 1564 Sum It Up | zoj 1711 | hdu 1548 (dfs + 剪枝 or 判重)


下一篇:6、Java并发编程:volatile关键字解析