Most Powerful

Time Limit: 2 Seconds

Memory Limit: 65536 KB

Recently, researchers on Mars have discovered N powerful atoms. All of them are different. These atoms have some properties. When two of these atoms collide, one of them disappears and a lot of power is produced. Researchers know the way every two atoms perform when collided and the power every two atoms can produce.

You are to write a program to make it most powerful, which means that the sum of power produced during all the collides is maximal.

**Input**

There are multiple cases. The first line of each case has an integer N (2 <= N <= 10), which means there are N atoms: A_{1}, A_{2}, … , A_{N}. Then N lines follow. There are N integers in each line. The j-th integer on the i-th line is the power produced when A_{i} and A_{j} collide with A_{j} gone. All integers are positive and not larger than 10000.

The last case is followed by a 0 in one line.

There will be no more than 500 cases including no more than 50 large cases that N is 10.

**Output**

Output the maximal power these N atoms can produce in a line for each case.

**Sample Input**

2

0 4

1 0

3

0 20 1

12 0 1

1 10 0

0

**Sample Output**

4

22

Author:

GAO, Yuan

Contest: ZOJ Monthly, February 2011

Question link:http://acm.zju.edu.cn/onlinejudge/showProblem.do?problemCode=3471

Title: N particles, AI and AJ collisions will generate AIJ energy at the same time AJ disappear, to the maximum energy that can be produced in the end

Question analysis: After seeing the amount of data, the obvious pressure is obvious. DP [i] indicates the maximum energy when the status is i. The status is: 1 is 1. Use, then enumerate the state, choose two different particles that are not used to try to collide

dp equations are dp [i | (1 << k)] = max (dp [i | (1 << k)], dp [i] + a [j] [k]), where I represents the state,, I represent status,,, I represent status,, I represent status,, I represent status,, I represent status,,, I represent status,, I represent status,, I represent status,, I represent status,,, I represent status,, I represent status. K indicates the latter particles of collision, J means the first particles of the collision

```
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
int n, a[15][15];
int dp[1 << 11];
int main()
{
while(scanf("%d", &n) != EOF && n)
{
for(int i = 0; i < n; i++)
for(int j = 0; j < n; j++)
scanf("%d", &a[i][j]);
memset(dp, 0, sizeof(dp));
for(int i = 0; i < (1 << n); i++)
for(int j = 0; j < n; j++)
if(!(i & (1 << j)))
for(int k = 0; k < n; k++)
if(j != k && !(i & (1 << k)))
dp[i | (1 << k)] = max(dp[i | (1 << k)], dp[i] + a[j][k]);
int ans = 0;
for(int i = 0; i < (1 << n); i++)
ans = max(ans, dp[i]);
printf("%d\n", ans);
}
}
```