2403: Simple Problem Again
| Result | TIME Limit | MEMORY Limit | Run Times | AC Times | JUDGE |
|---|---|---|---|---|---|
 |
3s | 8192K | 530 | 106 | Standard |
Everyone knows WeiXiaobao has seven wives. He is happy, but also has a lot of trouble.
He has a 7*7 plots of land,and he want to built seven houses for his wifes in his 49 small lands.Each row and coloum cannot have more than one house.(We know women like to feel jealous.) Different plots have different construction costs.He wanted to know how to build houses can let the money spent at most.(because he loves his wifes ,and believes that the more expensive the houses is ,the less trouble will be.)
Mars is an outstanding mathematician,and also is a friend of WeiXiaobao.After solved Weixiaobao's difficulty,he thought, if WeiXiaobao had n wives, and had n*n plots of land. How he should solve this problem .
Input
The first line has a positive number n(n<14).then followed n rows, each row has n positive integer(<300).The i+1 line j number represent the cost in (i,j).
Output
For each input data ouput the max cost.
Sample Input
3 1 2 3 3 2 1 2 3 2
Sample Output
9
Hint: he should build his houses in (1,3),(2,1),(3,2).
Problem Source: provided by AC2006
This problem is used for contest: 85
#include<stdio.h>
#include<string.h>
int n,max;
int map[14][14],b[14];
bool f[14];
void dfs(int depth,int nowcost)
{
int i;
if(depth>n)
{
if(nowcost>max) max=nowcost;
return;
}
if(nowcost+b[n]-b[depth-1]<max) return;
for(i=1;i<=n;i++)
if(!f[i])
{
f[i]=true;
dfs(depth+1,nowcost+map[depth][i]);
f[i]=false;
}
}
int main()
{
int i,j;
while(scanf("%d",&n)!=EOF)
{
memset(f,false,sizeof(f));
memset(b,0,sizeof(b));
for(i=1;i<=n;i++)
{
max=0;
for(j=1;j<=n;j++)
{
scanf("%d",&map[i][j]);
if(max<map[i][j]) max=map[i][j];
}
if(i==1) b[i]=max;
else b[i]=b[i-1]+max;
}
max=0;
dfs(1,0);
printf("%d/n",max);
}
return 0;
}