【做题】uoj#370滑稽树上滑稽果—

一个显然的结论是最终树的形态必然是一条链。具体证明只要考虑选定树上的某一条链，然后把其他部分全部接在它后面，这样答案一定不会变劣。

那么，一开始的想法是考虑每一位的最后出现位置，但这并不容易实现。注意到最终序列是单调递减的。我们在统计答案之前，把公共位先统计掉，即始终都是1的位。这样，剩下的位的最终结果都是0。这样，我们就避免了在统计时忽略某些数。那么，我们记dp[i]表示当前的结果为i的最小费用。我们在转移时枚举下一个数字是什么。这里无需担心数字的重复放置，因为它并不能让当前的数字发生变化。那么，我们就有如下第5档部分分。

memset(dp,0x3f,sizeof dp);

for (int i = 1 ; i <= n ; ++ i)

  dp[arr[i]] = arr[i];

for (int i = MAX - 1 ; i >= 1 ; -- i)

  for (int j = 1 ; j <= n ; ++ j)

    if ((i & arr[j]) < i)

      dp[i&arr[j]] = min(dp[i&arr[j]],dp[i] + (i&arr[j]));

注意到这里需要(i&arr[j])<i，即\(C_uarr[j] \bigcap i \neq \emptyset\)。那么，我们把所有\(C_uarr[j]\)的子集存下来，然后转移时枚举子集就做到dp时复杂度与n无关了。

时间复杂度大概是：\(O(a^{log_23})\)。

看起来很爆炸，但是非常不满。

#include <bits/stdc++.h>

#define rint register int

using namespace std;

typedef long long ll;

const int N = 200010, MAX = 1 << 18;

int arr[N],n,avail[MAX + 5],com;

ll dp[MAX + 5];

#define rev(x) ((x) ^ (MAX - 1))

int main() {

  com = MAX - 1;

  scanf("%d",&n);

  for (rint i = 1 ; i <= n ; ++ i)

    scanf("%d",&arr[i]), com &= arr[i];

  for (rint i = 1 ; i <= n ; ++ i)

    arr[i] ^= com;

  for (rint i = 1 ; i <= n ; ++ i) {

    if (avail[rev(arr[i])]) continue;

    for (rint j = rev(arr[i]) ; j ; j = (j-1) & rev(arr[i]))

      avail[j] = 1;

  }

  memset(dp,0x3f,sizeof dp);

  for (rint i = 1 ; i <= n ; ++ i) dp[arr[i]] = arr[i];

  for (rint i = MAX-1 ; i >= 1 ; -- i) if (dp[i] < dp[0]) {

    for (rint j = i ; j ; j = (j-1) & i) if (avail[j])

      dp[i^j] = min(dp[i^j],dp[i] + (0ll^i^j));

  }

  printf("%lld\n",1ll * com * n + dp[0]);

  return 0;

}

小结：抓住题目的特殊性质是优化的关键。

巴特西

【做题】uoj#370滑稽树上滑稽果——巧妙dp

最新文章

热门文章