fork download 
  1. #include <bits/stdc++.h> 
  2. using namespace std;  
  3.  
  4. typedef long long ll;  
  5. typedef pair<int, int> ii;  
  6.  
  7. const int INF = 1e9;  
  8. const ll LINF = 1e18;  
  9.  
  10. template<typename T>
  11. void maximize(T& a, const T& b) {
  12. 	if (a < b) a = b;  
  13. }
  14.  
  15. int n;  
  16. int a[16][16];  
  17. ll dp[1 << 16]; // dp[mask] = Tổng điểm lớn nhất có thể đạt được khi chia nhóm cho các chú thỏ có trong mask
  18.  
  19. int main() {
  20. 	ios::sync_with_stdio(0); cin.tie(0);  	
  21. 	cin >> n;
  22. 	for (int i = 0; i < n; i++) {
  23. 		for (int j = 0; j < n; j++) cin >> a[i][j]; 
  24. 	}
  25.  
  26. 	// Trường hợp các chú thỏ có trong mask cùng thuộc chung một nhóm
  27. 	for (int mask = 0; mask < (1 << n); mask++) {
  28. 		ll tot = 0;  
  29. 		for (int i = 0; i + 1 < n; i++) {
  30. 			if (!(mask & (1 << i))) continue; 
  31. 			for (int j = i + 1; j < n; j++) {
  32. 				if (!(mask & (1 << j))) continue; 
  33. 				tot += a[i][j]; 
  34. 			}
  35. 		}
  36. 		dp[mask] = tot; 
  37. 	}
  38.  
  39. 	// Trường hợp các chú thỏ có trong mask được chia thành các nhóm nhỏ hơn
  40. 	for (int mask = 1; mask < (1 << n); mask++) {
  41. 		for (int submask = mask; submask > 0; submask = (submask - 1) & mask) {
  42. 			maximize(dp[mask], dp[submask] + dp[mask ^ submask]); 
  43. 		}
  44. 	}
  45.  
  46. 	cout << dp[(1 << n) - 1] << '\n'; 
  47. }
Success #stdin #stdout 0.01s 5284KB
comments (?)
stdin 
3
0 10 20
10 0 -100
20 -100 0
stdout 
20
https://ideone.com/haoVK3
language:
C++14 (gcc 8.3)
created:
13 days ago
visibility:
secret

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!