首页 > 代码库 > BZOJ1150 [CTSC2007]数据备份Backup
BZOJ1150 [CTSC2007]数据备份Backup
这是一道很好的题目，正常人都想不出做法。
我还记得题解是说：
(1)想到动规，但是T到死。。。
(2)转化成网络流，还是T的不行
(3)咦，好像是贪心欸，做出来了（你在卖萌！）
其实算法很简单，首先我们知道必须找相邻的两个进行配对，但是不是直接找最小，而是每次要找最短的一段（后面会解释什么叫"段"），于是可以用堆来维护。
具体做法是找出当前最短的段X，设左边那段叫L，右边那段叫R，那么:
只要(1)ans += dis[X] (2)删除X、L、R三段，即堆中删除dis[X], dis[L], dis[R] (3)堆中加入dis[L] + dis[R] - dis[X]即可
删除我用的是时间标记法，比较容易实现。
什么叫段：就是i到j之间的全部都两两配对形成最小值的区间的啊。。
一开始有n - 1段，每次操作会造成减少两段，这是合理的，下面会解释。
算法合理性解释：
如果你取了一段X，但是其实取左右L和R比现在更优，那么下一次你会取L + R - X这一"段", 最后的ans = dis[L] + dis[R]，也就是取了L和R。
这就解释了为什么会操作一次减少两段，因为后面如果选了dis[L] + dis[R] - dis[X]这段等于一下子选了两段，所以前面就会先减掉1段。
1 #include <cstdlib> 2 #include <cstdio> 3 #include <queue> 4 #include <utility> 5 #include <cstring> 6 #include <vector> 7 8 const int arr = 200000; 9 using namespace std;10 typedef pair<int, pair <int, int> > PP;11 12 priority_queue <PP> heap;13 int n, K, ans, L, R, pos, l[arr], r[arr], t[arr], a[arr];14 bool v[arr];15 16 int main(){17 int maxn = 2000000000;18 scanf("%d%d", &n, &K);19 for (int i = 1; i <= n; ++i)20 scanf("%d", a + i);21 for (int i = n; i > 1; --i)22 a[i] -= a[i - 1];23 24 a[1] = a[++n] = maxn;25 26 while (!heap.empty()) heap.pop();27 for (int i = 1; i <= n; ++i){28 heap.push(make_pair(-a[i], make_pair(i, 1)));29 l[i] = i - 1, r[i] = i + 1, t[i] = 1;30 }31 memset(v, 0, sizeof(v));32 33 PP x;34 ans = 0;35 while (K--){36 for (x = heap.top(); v[x.second.first] || x.second.second != t[x.second.first]; heap.pop(), x = heap.top());37 x = heap.top();38 ans -= x.first;39 pos = x.second.first;40 L = l[pos], R = r[pos];41 r[L] = r[R];42 l[r[R]] = L;43 v[pos] = v[R] = 1;44 a[L] += a[R] - a[pos];45 heap.push(make_pair(-a[L], make_pair(L, ++t[L])));46 }47 printf("%d\n", ans);48 return 0;49 }
非常丑陋的代码。。。正常人看不懂系列。。（话说hzwer:"堆的精确删点我还不会，于是就用SBT做了。。。"，简直超神。。。）
BZOJ1150 [CTSC2007]数据备份Backup
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。