BOJ 21943 - 연산 최대로

BOJ 21943 - 연산 최대로

그냥 Bitmask DP로 풀었는데, 생각해보니 그리디가 된다.

풀어보진 않았지만 대략 다음과 같을 거라고 생각한다.

곱하기를 쓸 수 있는 횟수는 정해져 있고 그걸 $m$ 이라 하자.

그럼 $m+1$ 개의 수들을 곱해야 한다는 의미인데, 그럼 $p$ 개의 더하기들을 이용해서 $m+1$ 개의 수들을 완전탐색으로 가능한 경우를 모두 찾아낸다음 풀면 되지않을까

int bcnt(ll x) { return __builtin_popcountll(x); }
int rz(ll x) { return __builtin_ctzll(x); }
int lz(ll x) { return __builtin_clzll(x); }
int msb(ll x) { return 63 - lz(x); }
void solve() {
   int n;
   cin >> n;
   vi a(n);
   fv(a);
   int p, q;
   cin >> p >> q;

   vvi masks(n + 1);
   for (int mask = 0; mask < (1 << n); mask++) masks[bcnt(mask)].pb(mask);

   debug(masks);
   vector<vector<set<int>>> nums(1 << n, vector<set<int>>(p + 1));
   for (int i = 0; i < n; i++) nums[1 << i][0].insert(a[i]);
   for (int len = 2; len <= n; len++) {
      for (int len1 = 1; len1 < len; len1++) {
         int len2 = len - len1;
         for (int mask1: masks[len1]) {
            for (int mask2: masks[len2]) {
               int mask = mask1 | mask2;
               if ((mask1 & mask2) == 0) {
                  for (int p1 = 0; p1 <= len1 - 1; p1++) {
                     for (int p2 = 0; p2 <= len2 - 1; p2++) {
                        if (p1 + p2 <= p) {
                           for (int a: nums[mask1][p1]) {
                              for (int b: nums[mask2][p2]) {
                                 if (p1 + p2 < p)
                                    nums[mask][p1 + p2 + 1].insert(a + b);
                                 nums[mask][p1 + p2].insert(a * b);
                              }
                           }
                        }
                     }
                  }
               }
            }
         }
      }
      debug(len);
   }
   int ans = 0;
   for (auto &s: nums) {
      for (int i: s[p]) {
         maxa(ans, i);
      }
   }
   cout << ans;
}