fork download
copy 
  1. import java.util.Scanner;
  2.  
  3. public class Main {
  4. 	static Scanner in = new Scanner(System.in);
  5.  
  6. 	static int[][] a = new int[20][20];
  7. 	static int[][] bit = new int[20][20];
  8. 	static int[][] dp = new int[20][20];
  9.  
  10. 	static void solve() {
  11. 		int n = in.nextInt();
  12. 		for (int i = 0; i < n; ++i) {
  13. 			for (int j = 0; j < n; ++j) {
  14. 				a[i][j] = in.nextInt();
  15. 				if (i == 0) {
  16. 					dp[i][j] = a[i][j];
  17. 					bit[i][j] = 1 << j;
  18. 				}
  19. 			}
  20. 		}
  21.  
  22. 		int res = 0;
  23. 		for (int i = 1; i < n; ++i) {
  24. 			for (int j = 0; j < n; ++j) {
  25. 				dp[i][j] = 0;
  26. 				for (int k = 0; k < n; ++k) {
  27. 					if (((1 << j) & bit[i - 1][k]) == 0) {
  28. 						int cur = dp[i - 1][k] + a[i][j];
  29. 						if (cur > dp[i][j]) {
  30. 							dp[i][j] = cur;
  31. 							bit[i][j] = bit[i - 1][k] + (1 << j);
  32. 						}
  33. 					}
  34. 				}
  35. 				res = Integer.max(res, dp[i][j]);
  36. 			}
  37. 		}
  38.  
  39. 		System.out.println(res);
  40. 	}
  41.  
  42. 	public static void main(String[] args) {
  43. 		int t = 1;
  44. 		t = in.nextInt();
  45. 		while (t-- > 0) solve();
  46. 	}
  47. }
Success #stdin #stdout 0.15s 56556KB
comments (?)
stdin
copy 
2
3
3 1 2
1 1 2
1 4 2
2
1 2
2 1
stdout
copy 
9
4
https://ideone.com/vCdrrg
language:
Java (HotSpot 12)
created:
1 day 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!