Untitled
unknown
plain_text
a year ago
949 B
7
Indexable
#include<iostream> using namespace std; int n; int a[11]; int dp[11111]; int max(int a, int b){ if (a < b) return b; return a; } int dfs(int bit){ if (bit == 0) return 0; if (dp[bit]) return dp[bit]; int p = 0; int b[11]; for (int i = 0; i < n; i++){ if ((bit >> i) & 1) b[p++] = i; } int mx = 0; for (int i = 0; i < p; i++){ int v; if (i - 1 >= 0 && i + 1 < p) v = a[b[i - 1]] * a[b[i + 1]]; else if (i - 1 >= 0) v = a[b[i - 1]]; else if (i + 1 < p) v = a[b[i + 1]]; else v = a[b[i]]; mx = max(mx, dfs(bit ^ (1 << b[i])) + v); } dp[bit] = mx; return mx; } void solve(int test){ cin >> n; for (int i = 0; i < n; i++) cin >> a[i]; int lim = 1 << n; for (int i = 0; i < lim; i++) dp[i] = 0; cout << "Case #" << test << '\n' << dfs(lim - 1) << '\n'; } int32_t main(){ int t = 1; cin >> t; for (int i = 1; i <= t; i++) solve(i); }
Editor is loading...
Leave a Comment