fork download 
  1. #include<iostream>
  2. #include<queue> 
  3. #include<stack>
  4. #include<list>
  5. #include<iomanip>
  6. #include<string>
  7. #include<map>
  8. #include<set>
  9. #include<vector>
  10. #include<algorithm>
  11. #include<math.h>
  12. #include<stdio.h>
  13. #include<cstring>
  14. #include<fstream>
  15. #include<stdlib.h>
  16. #include<sstream>
  17. #define INF (1 << 30) 
  18. #define N (11) 
  19.  
  20. using namespace std;
  21.  
  22. int matrix[N][N];
  23. int dp[N][(1 << N)];
  24.  
  25. //                 bitmask      
  26. int F(int stage, int selecion)
  27. {
  28.   if(stage == N) return selecion == (1<<N)-1 ? 0 : -INF;
  29.  
  30.   if(dp[stage][selecion] != -1)
  31.     return dp[stage][selecion];
  32.  
  33.   int answer = -INF;
  34.  
  35.   for(int i = 0;i < N;i++)
  36.     if((selecion & (1 << i)) == 0) 
  37.         answer = max(answer, matrix[i][stage] + F(stage+1, selecion | (1 << i) ) );
  38.  
  39.   dp[stage][selecion] = answer;
  40.  
  41.   return answer;
  42. }
  43.  
  44. int main()
  45. {
  46.   int t,n;
  47.  
  48.   scanf("%d",&t);
  49.  
  50.   while(t--)
  51.   {
  52.   	scanf("%d",&n);
  53.  
  54.     for(int i = 0;i < n;i++)
  55.       for(int j = 0;j < n;j++)
  56.         scanf("%d",&matrix[i][j]);
  57.  
  58.     memset(dp, -1, sizeof dp);
  59.  
  60.     printf("%d\n",F(0,0));
  61.   }
  62.  
  63.   return 0;
  64. }
  65.  
Success #stdin #stdout 0s 3432KB
comments (?)
stdin 
1
4
7   53  183 439
627 343 773 959
447 283 463 29
217 623 3   399
stdout 
2282
https://ideone.com/vchrwa
language:
C++ (gcc 8.3)
created:
11 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!