Lightoj 1011 - Marriage Ceremonies

http://lightoj.com/volume_showproblem.php?problem=1011

1. #include <bits/stdc++.h>
2. using namespace std;
3. int dp[18][1<<18], n;
4. #define check(n, pos) (n & (1<<pos))
5. #define sett(n, pos) (n | (1<<pos))
6. int a[18][18];
7. int go(int i, int mask){
8.     if(i == n){
9.         return 0;
10.     }
11.     if(dp[i][mask] != -1){
12.         return dp[i][mask];
13.     }
14.     int ans = -1;
15.     for(int j = 0; j <n;j++){
16.         if(!check(mask, j)){
17.             ans = max(ans, a[i][j] + go(i+1,sett(mask, j)));
18.         }
19.     }
20.     return dp[i][mask] = ans;
21. }
22.  
23. int main()
24. {
25.     int ts, cs = 1;
26.     cin>>ts;
27.     while(ts--){
28.     cin>>n;
29.     memset(dp, -1, sizeof(dp));
30.     for(int i = 0; i<n; i++){
31.         for(int j = 0; j <n; j++){
32.             cin>>a[i][j];
33.         }
34.     }
35.     printf("Case %d: %d\n",cs, go(0, 0));
36.     cs++;
37.     }
38.     return 0;
39. }