Help in a GCD problem

Блог пользователя DC-HITMAN

Автор DC-HITMAN, история, 6 лет назад, По-английски

I got stuck in a problem and need a little bit help

So the problem is you are given an array of size n (n is always even) and In each move, you can remove any two elements from the array and each move will contribute gcd(removed_val_1, removed_val_2) * move_number So we have to maximize the score I don't know the constraints on N but arr[i] <= 10^5

#gcd

DC-HITMAN
6 лет назад
5

Комментарии (4)

Показать архивные | Написать комментарий?

som

6 лет назад, скрыть # |

N is <=20

→ Ответить

Not-Afraid

6 лет назад, скрыть # ^ |

then it will be just trivial bitmask dp if I am not missing something.

→ Ответить

stmlstmlstmlstml

6 лет назад, скрыть # ^ |

← Rev. 4 →

→ Ответить

Not-Afraid

6 лет назад, скрыть # ^ |

← Rev. 2 →

Spoiler

// O(2 ^ N * (N ^ 2))

// Love the way you Lie.

#include <bits/stdc++.h>

using namespace std;

int n;
int dp[1 << 20];
vector<int> a;

int go(int mask) {
	int used = __builtin_popcount(mask);
	// array becomes empty
	if (used == n) {
		return 0;
	}
	// memoize
	if (dp[mask] != -1) {
		return dp[mask];
	}
	int cur_move = used / 2 + 1;
	int ans = 0;
	for (int i = 0; i < n; ++i) {
		for (int j = i + 1; j < n; ++j) {
			if (!(mask >> i & 1) && !(mask >> j & 1)) {
				int points = __gcd(a[i], a[j]) * cur_move;
				int rem = go(mask | (1 << i) | (1 << j));
				ans = max(ans, rem + points);
			}
		}
	}
	return dp[mask] = ans;
}


void solve() {
	cin >> n;
	memset(dp, -1, sizeof dp);
	a.resize(n);
	assert(n % 2 == 0);
	for (int i = 0; i < n; ++i) {
		cin >> a[i];
	}	
	cout << go(0);
}

#define single_test

signed main() {
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    int t = 1;
    #ifndef single_test
        cin >> t;
    #endif
    for (int i = 1; i <= t; ++i) {
        // cout << "Case #" << i << ": ";
        solve();
    }
    return 0;
}

→ Ответить