LOJ2323. 「清华集训 2017」小 Y 和地铁【搜索】【思维】【好】

思路

首先如果直接算每一个段有三个决策

左/右上/下跨不跨过端点

这样的复杂度是\((2^3)^{22}\)，显然是无法接受的

然后考虑怎么优化这个东西

首先左右这个决策是没有意义的

因为无论是左还是右，对答案的相对影响是不变的

其次考虑用a和b分别表示上下和跨不跨过端点的决策

然后退一下就可发现有很多种情况是可以归约的

大概成了这样

void dfs(int tmp, int res) {

  if (res >= ans) return;

  if (tmp > n) {

    ans = res;

    return;

  }

  if (cnt[t[tmp]] == 1 || pre[tmp]) {

    dfs(tmp + 1, res);

    return;

  }

  int now;

  a[tmp] = 0;

  b[tmp] = 0;

  now = res;

  fu(i, 1, tmp - 1)

    if (!(a[i] ^ b[i]) && nxt[i] > tmp && nxt[i] < nxt[tmp]) ++now;

  dfs(tmp + 1, now);

  a[tmp] = 0;

  b[tmp] = 1;

  now = res;

  fu(i, 1, tmp - 1) {

    if ((a[i] ^ b[i]) && nxt[i] > nxt[tmp]) ++now;

    if (!(a[i] ^ b[i]) && nxt[i] > tmp) ++now;

  }

  dfs(tmp + 1, now);

  a[tmp] = 1;

  b[tmp] = 0;

  now = res;

  fu(i, 1, tmp - 1)

    if ((a[i] ^ b[i]) && nxt[i] > tmp && nxt[i] < nxt[tmp]) ++now;

  dfs(tmp + 1, now);

  a[tmp] = 1;

  b[tmp] = 1;

  now = res;

  fu(i, 1, tmp - 1) {

    if (!(a[i] ^ b[i]) && nxt[i] > nxt[tmp]) ++now;

    if ((a[i] ^ b[i]) && nxt[i] > tmp) ++now;

  }

  dfs(tmp + 1, now);

}

这样是可以得到64分的高分的

但是并不够

继续考虑怎么压缩状态

发现前面的每个已经决策的区间对当前区间的影响只有a和b的异或和

所以每次只枚举a和b的异或和

但是a和b的异或和相等的情况有两种

但是这两种对后面决策的影响都是相同的

所以直接贪心取最小的就可以了

复杂度\(n*2^{n/2}\)

AC代码

//Author: dream_maker

#include<bits/stdc++.h>

using namespace std;

//----------------------------------------------

//typename

typedef long long ll;

//convenient for

#define fu(a, b, c) for (int a = b; a <= c; ++a)

#define fd(a, b, c) for (int a = b; a >= c; --a)

#define fv(a, b) for (int a = 0; a < (signed)b.size(); ++a)

//inf of different typename

const int INF_of_int = 1e9;

const ll INF_of_ll = 1e18;

//fast read and write

template <typename T>

void Read(T &x) {

  bool w = 1;x = 0;

  char c = getchar();

  while (!isdigit(c) && c != '-') c = getchar();

  if (c == '-') w = 0, c = getchar();

  while (isdigit(c)) {

    x = (x<<1) + (x<<3) + c -'0';

    c = getchar();

  }

  if (!w) x = -x;

}

template <typename T>

void Write(T x) {

  if (x < 0) {

    putchar('-');

    x = -x;

  }

  if (x > 9) Write(x / 10);

  putchar(x % 10 + '0');

}

//----------------------------------------------

const int N = 50;

int t[N], n, ans;

int pre[N], nxt[N], last[N], cnt[N];

bool a[N], b[N], mark[N];

//a 走上面(0)还是下面(1)

//b 不跨过(0)还是跨过(1)

int T;

/*void dfs(int tmp, int res) {

  if (res >= ans) return;

  if (tmp > n) {

    ans = res;

    return;

  }

  if (cnt[t[tmp]] == 1 || pre[tmp]) {

    dfs(tmp + 1, res);

    return;

  }

  int now;

  a[tmp] = 0;

  b[tmp] = 0;

  now = res;

  fu(i, 1, tmp - 1)

    if (!(a[i] ^ b[i]) && nxt[i] > tmp && nxt[i] < nxt[tmp]) ++now;

  dfs(tmp + 1, now);

  a[tmp] = 0;

  b[tmp] = 1;

  now = res;

  fu(i, 1, tmp - 1) {

    if ((a[i] ^ b[i]) && nxt[i] > nxt[tmp]) ++now;

    if (!(a[i] ^ b[i]) && nxt[i] > tmp) ++now;

  }

  dfs(tmp + 1, now);

  a[tmp] = 1;

  b[tmp] = 0;

  now = res;

  fu(i, 1, tmp - 1)

    if ((a[i] ^ b[i]) && nxt[i] > tmp && nxt[i] < nxt[tmp]) ++now;

  dfs(tmp + 1, now);

  a[tmp] = 1;

  b[tmp] = 1;

  now = res;

  fu(i, 1, tmp - 1) {

    if (!(a[i] ^ b[i]) && nxt[i] > nxt[tmp]) ++now;

    if ((a[i] ^ b[i]) && nxt[i] > tmp) ++now;

  }

  dfs(tmp + 1, now);

}*/

void dfs(int tmp, int res) {

  if (res >= ans) return;

  if (tmp > n) {

    ans = res;

    return;

  }

  if (cnt[t[tmp]] == 1 || pre[tmp]) {

    dfs(tmp + 1, res);

    return;

  }

  int now1, now2;

  mark[tmp] = 0;

  now1 = now2 = res;

  fu(i, 1, tmp - 1) {

    if (!mark[i] && nxt[i] > tmp && nxt[i] < nxt[tmp]) ++now1;

    if (!mark[i] && nxt[i] > nxt[tmp]) ++now2;

    if (mark[i] && nxt[i] > tmp) ++now2;

  }

  dfs(tmp + 1, min(now1, now2));

  mark[tmp] = 1;

  now1 = now2 = res;

  fu(i, 1, tmp - 1) {

    if (mark[i] && nxt[i] > tmp && nxt[i] < nxt[tmp]) ++now1;

    if (mark[i] && nxt[i] > nxt[tmp]) ++now2;

    if (!mark[i] && nxt[i] > tmp) ++now2;

  }

  dfs(tmp + 1, min(now1, now2));

}

void solve() {

  Read(n);

  fu(i, 1, n) pre[i] = nxt[i] = last[i] = cnt[i] = 0;

  fu(i, 1, n) {

    Read(t[i]);

    ++cnt[t[i]];

    if (last[t[i]]) {

      pre[i] = last[t[i]];

      nxt[last[t[i]]] = i;

    } else {

      last[t[i]] = i;

    }

  }

  ans = INF_of_int;

  dfs(1, 0);

  printf("%d\n", ans);

}

int main() {

  freopen("input.txt","r",stdin);

  Read(T);

  while (T--) solve();

  return 0;

}

巴特西

LOJ2323. 「清华集训 2017」小 Y 和地铁【搜索】【思维】【好】

思路

最新文章

热门文章

巴特西

LOJ2323. 「清华集训 2017」小 Y 和地铁 【搜索】【思维】【好】

思路

最新文章

热门文章

LOJ2323. 「清华集训 2017」小 Y 和地铁【搜索】【思维】【好】