Submission #64377726

---

Source Code Expand

#include <bits/stdc++.h>
#ifdef LOCAL
#include "Debug.h"
#else
#define debug(...) 42
#endif
using namespace std;
const long long oo = 1LL << 60;

int main()
{
  int n;
  cin >> n;
  vector<long long> a(n + 1), s(n + 1);
  for (int i = 1; i <= n; i++)
  {
    cin >> a[i];
    s[i] = s[i - 1] ^ a[i];
  }

  if (n == 1)
  {
    cout << a[1] << endl;
    return 0;
  }

  vector<vector<long long>> f(n + 2, vector<long long>(n + 2));
  for (int i = 1; i <= n; i++)
    f[i][i] = oo;

  for (int len = 2; len <= n; len++)
    for (int i = 1; i + len - 1 <= n; i++)
    {
      int j = i + len - 1;
      long long xorAll = s[j] ^ s[i - 1];
      f[i][j] = oo;
      for (int k = i + 1; k < j; k++)
      {
        long long curF = f[i][k] + f[k + 1][j];
        if (k % 2 == i % 2)
          curF += xorAll;
        if (k % 2 != j % 2)
          curF += xorAll;
        f[i][j] = min(f[i][j], curF);
      }

      if (len % 2)
      {
        for (int k = i; k <= j; k += 2)
          f[i][j] = min(f[i][j], f[i][k - 1] + f[k + 1][j]);
      }
      else
      {
        for (int k = i; k <= j; k++)
          if (k % 2 == i % 2)
          {
            f[i][j] = min(f[i][j], f[i][k - 1] + f[k + 1][j - 1] + xorAll * 2);
            f[i][j] = min(f[i][j], f[i][k - 1] + f[k + 2][j] + xorAll * 2);
          }
          else
          {
            f[i][j] = min(f[i][j], f[i + 1][k - 1] + f[k + 1][j] + xorAll * 2);
          }
      }
    }

  if (n % 2)
    f[1][n] += s[n];
  cout << f[1][n] << endl;
}

Submission Info

Judge Result